


Решение задачи в Excel методом динамического программирования
Необходимо написать решение задачи в Excel методом динамического программирования с помощью формул Excel.
Задание звучит так: Какое наименьшее количество слагаемых потребуется, чтобы представить число 96, если каждое слагаемое равно либо 3, либо 4, либо 7?
12*7+3*4
12+3=15 слагаемых. На хрена тут применять динамическое программирование, если задача решается в уме за полсекунды?
Для решения этой задачи методом динамического программирования в Excel, мы можем использовать следующий подход:
1. **Инициализация таблицы**: Создайте таблицу, где каждая строка соответствует одному из возможных слагаемых (3, 4, 7), а столбцы - числам от 1 до 96 (или до меньшего числа, если вы уверены, что решение найдется раньше).
2. **Заполнение таблицы**: Для каждой ячейки таблицы вычислите минимальное количество слагаемых, необходимых для получения числа, соответствующего столбцу, используя только слагаемые из текущей строки и выше. Формула для ячейки будет зависеть от значения слагаемого и значений в предыдущих ячейках.
3. **Формулы**:
- Если текущее число меньше слагаемого, то копируем значение из ячейки выше.
- Если текущее число равно слагаемому, то записываем 1, так как число можно представить одним слагаемым.
- Если текущее число больше слагаемого, то минимум из двух значений: значение из ячейки выше или (1 + значение из ячейки в этой строке, но для числа, уменьшенного на текущее слагаемое).
4. **Реализация в Excel**:
- В первой строке (заголовки столбцов) укажите числа от 1 до 96.
- В первом столбце (заголовки строк) укажите слагаемые 3, 4, 7.
- Заполните таблицу согласно описанным правилам.
Пример формулы для ячейки, соответствующей слагаемому 3 и числу 10:
- Если в ячейке выше (для слагаемого 4 и числа 10) стоит значение \( X \), и в ячейке этой же строки, но для числа 7 (10 - 3 = 7), стоит значение \( Y \), то в текущей ячейке будет минимум из \( X \) и \( Y + 1 \).
После заполнения таблицы, минимальное количество слагаемых для представления числа 96 будет в ячейке, соответствующей слагаемому 7 и числу 96.