Учитывая обычный n
наборов элементов (каждый неограниченный, скажем), с весами и значениями:
w1, v1
w2, v2
...
wn, vn
и целевым весом W
, мне нужно выбрать элементы таким образом, чтобы общий вес
составляет не менее Вт
, а общее значение минимизировано .
Мне это кажется разновидностью (или в некотором смысле наоборот) задачи о целочисленном / неограниченном рюкзаке. Мы будем очень благодарны за любую помощь в формулировании алгоритма DP !