Change on backpack - minimum total value greater than 'W'

Question

For ordinary n sets of elements (each without restrictions, say) with weights and values:

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

and the target weight is W , I need to select elements such that the sum of the weight is not less than W , and the total value is minimized .

It looks like a variation (or in a sense the flip side) of an integer / unlimited knapsack problem. Any help with formulating the DP algorithm would be greatly appreciated!

Answer 1

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

In this answer I will describe the second bag. I will designate the original as “bag” and optional as “backpack”

Fill the bag with all the elements and start to exclude elements from it, "filling out" a new <early backpack with a size of no more than TOT-W with the highest possible value! You have a problem with a regular backpack, with the same elements and size of a TOT-W bag.

Evidence:
Suppose you have a better solution with k elements: e_i1,e_i2,...,e_ik , then the size of the bag is not less than the size W , which makes the excluded items a satchel no more than the size of TOT-W . In addition, since the knapsack value is minimized for the size W , the value of the excluded elements is maximized for the TOT-W size, since if it were not the maximum, there would be a better bag of at least W size, with a smaller value.
Another way [assuming you have the maximum excluded bag] is almost identical.

Answer 2

Not too sure, but it might work. Consider the values ​​as -ve values ​​that you have. Composition DP will try to find the maximum value for this weight, which in this case would be the least negative. When you have a meaning, take it for the final answer.