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

Question

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

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

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

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

Answer 1

let TOT = w1 + w2 + ... + wn.

В этом ответе я опишу вторую сумку.Я обозначу оригинал как «мешок», а дополнительный как «рюкзак»

Заполните сумку всеми элементами и начните исключать из нее элементы, «наполняя» новый рюкзак с размером не более TOT-W, с максимально возможным значением!У вас есть обычная проблема с рюкзаком, с такими же элементами и размером сумки TOT-W.

Доказательство:
Предположим, у вас есть лучшее решение с k элементами: e_i1,e_i2,...,e_ik,тогда размер мешка будет не менее размера W, что делает рюкзак из исключенных предметов максимально по размеру TOT-W.Кроме того, поскольку значение ранца минимизировано для размера W, значение исключенных предметов максимально увеличено для размера TOT-W, потому что, если бы оно не было максимизировано, был бы лучший мешок размера, по крайней мере, W, с меньшим значением.
Обратный путь [при условии, что у вас есть максимально исключенная сумка] практически идентичен.

Answer 2

Не слишком уверен, но это может сработать.Считайте, что значения являются -ve значений, которые у вас есть.Формула DP будет пытаться найти максимальное значение для этого веса, который будет наименее отрицательным значением в этом случае.Когда у вас есть значение, возьмите его для окончательного ответа.