Ответ в теме: Задача о ранце методом динамического программирования

      Комментарии к записи Ответ в теме: Задача о ранце методом динамического программирования отключены
#2266

На основе формулы возможно построить таблицу, отложив по строкам предметы, а по столбцам — вес. В каждой клетке таблицы записывается значение цены рюкзака. Первая строка таблицы будет содержать нули, т.к. не соответствует никакому предмету, однако она необходима для расчета других строк по формуле. Аналогично, первый столбец, соответствует рюкзаку нулевой вместимости, поэтому содержит одни нули. Когда таблица будет построена, оптимальное решение будет находиться в правой нижней клетке, из которой, следуя по вертикали или горизонтали в направлении наибольшего значения, можно восстановить решение (набор предметов Bag).

На рисунке [1] приведен пример построения таблицы для предметов стоимости Cost = [ 55, 80, 60, 45, 105, 50 ] и веса Weight = [ 3, 2, 4, 1, 3, 105 ].

Литература:

  1. Дж. Макконелл Анализ алгоритмов. Активный обучающий подход. — 3-е дополненное издание. М: Техносфера, 2009. -416с.