58
правок
Изменения
→Другие задачи семейства
Заполним <tex>d(0,c)</tex> нулями.
Тогда меняя i от 1 до <tex>N</tex>, расчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex> , по рекурентной формуле:
<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i : l\ integer</tex> <math>0 \le l \le min(b_i,\lfloor c/w_i \rfloor))</math>
Заполним <tex>d(0,c)</tex> нулями.
Тогда меняя i от 1 до <tex>N</tex>, расчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex> , по рекурентной формуле:
<tex>
Заполним <tex>d(0,c)</tex> нулями.
Тогда меняя i от 1 до <tex>N</tex>, расчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex> , по рекурентной формуле:
<tex>
==Задача о размене==
'''Задача о размене'''' (англ. ""''Change-Making problem'') - обобщение ограниченого рюкзакаимеются <tex> N </tex> не исчерпаемых типов предметов с весами <tex>w_i</tex>, нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>. Часто задачу ставят как, в котором любой предмет может быть выбран любое количество раздать сдачу наименьшим количеством монет.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы
<math> x_i \in {ge 0,1} </math>целое, для всех <math> i= 1,2,...,N</math>
===Варианты решения===
===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого количества вещей минимальное число премдетов, типов от 1 до <tex>i</tex>, суммарным весом до необходимое, чтобы заполнить рюкзак вместимостью <tex>c</tex> включительно .
Тогда меняя i от 1 до <tex>N</tex>, расчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex> , по рекурентной формуле:
<tex>
