Variation on knapsack - minimum total value exceeding 'W'
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!
Answer
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.