Вариация рюкзака - минимальная общая стоимость, превышающая 'W'

Учитывая обычный n наборов элементов (каждый неограниченный, скажем), с весами и значениями:

w1, v1
w2, v2
...
wn, vn

и целевым весом W , мне нужно выбрать элементы таким образом, чтобы общий вес составляет не менее Вт , а общее значение минимизировано .

Мне это кажется разновидностью (или в некотором смысле наоборот) задачи о целочисленном / неограниченном рюкзаке. Мы будем очень благодарны за любую помощь в формулировании алгоритма DP !

6
задан unutbu 14 January 2015 в 11:04
поделиться