Variation on knapsack - minimum total value exceed

问题:

Given the usual n sets of items (each unlimited, say), with weights and values:

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

and a target weight W, I need to choose items such that the total weight is at least W and the total value is minimized.

This looks to me like a variation (or in some sense converse) of the integer/unbounded knapsack problem. Any help in formulating the DP algorithm would be much appreciated!

回答1:

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

In this answer I will describe a second bag. I'll denote the original as 'bag' and to the additional as 'knapsack'

Fill the bag with all elements, and start excluding elements from it, 'filling' up a new knapsack with size of at most TOT-W, with the highest possible value! You got yourself a regular knapsack problem, with same elements, and bag size of TOT-W.

Proof:
Assume you have best solution with k elements: e_i1,e_i2,...,e_ik, then the bag size is at least of size W, which makes the excluded items knapsack at most at size TOT-W. Also, since the value of the knapsack is minimized for size W, the value of the excluded items is maximized for size TOT-W, because if it was not maximized, there would be a better bag of size at least W, with smaller value.
The other way around [assuming you have maximal excluded bag] is almost identical.

回答2:

Not too sure, but this might work. Consider the values to be the -ve of the values you have. The DP formulation would try to find max value for that weight which would be the least negative value in this case. Once you have a value, take a -ve of it for the final answer.