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

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

Пусть набор предметов Bag стоимости Cost веса Weight является решением задачи. Некоторый предмет Item стоимости ItemCost веса ItemWeight может:

  • входит в Bag, тогда множество Bag\{Item} (без выбранного предмета) имеет стоимость Cost-ItemCost и является решением задачи для меньшего числа предметов и рюкзака вместимости Weight-ItemWeight;
  • не входит в Bag, значит набор Bag является решением задачи с меньшим числом предметов.

Такое поведение описывается в виде формулы: