§ 45. Динамическое программирование

§ 45. Динамическое программирование

1. Напишите программу, которая определяет оптимальный набор бидонов в задаче 2 из параграфа. С клавиатуры или из вводится объем цистерны, количество бидонов и их размеры.
2. Напишите программу, которая решает задачу 3 о куче камней заданного веса, рассмотренную в тексте параграфа.

   *3. Задача о ранце. Есть N предметов, для каждого из которых известен вес р, (i = 1,..., N) и стоимость с₍ (£ = 1,..., JV). В ранец можно взять предметы общим весом не более №. Напишите программу, которая определяет самый дорогой набор предметов, который можно унести в ранце.

   4. У исполнителя Калькулятор две команды, которым присвоены номера:

1)прибавь   1

3)умножь    на    4

Напишите программу, которая вычисляет, сколько существует раз­личных программ, преобразующих число 1 в число JV, введённое с клавиатуры. Используйте сокращённую таблицу.

5. У исполнителя Калькулятор три команды, которым присвоены номе­
ра:

1)прибавь   1 2)умножь    на   3 3) умножь    на    4

Напишите программу, которая вычисляет, сколько существует раз­личных программ, преобразующих число 1 в число N, введённое с клавиатуры.

6. У   исполнителя   Калькулятор   две   команды,   которым   присвоены
номера:

1)прибавь   1

2) увеличь    каждый   разряд   числа    на    1

Сколько есть программ, которые число 24 преобразуют в число 46?

7. У   исполнителя   Калькулятор   две   команды,   которым   присвоены
номера:

1)прибавь    1

2) увеличь    каждый   разряд   числа   на    1

Сколько существует программ, которые число 26 преобразуют в число 49?

*8. Прямоугольный остров разделён на квадраты так, что его разме­ры — N * М квадратов. В каждом квадрате зарыто некоторое число золотых монет, эти данные хранятся в матрице (двумерном массиве) Z, где Z[i, J] — число монет в квадрате с координатами (i. j). Пират хочет пройти из юго-западного угла острова в северо-восточный, причём он может двигаться только на север или на восток. Как пи­рату собрать наибольшее количество монет? Напишите программу, которая находит оптимальный путь пирата и число монет, которое ему удастся собрать.