Least Weight for a Value Target
Each item has a weight and a value. Print the smallest total WEIGHT of a selection
whose total value is at least target, or -1 if no selection reaches it.
items (w=1000000000 v=3) (w=1000000000 v=4) (w=1 v=2), target = 5 -> 1000000001
## Why the usual table does not fit
Every knapsack so far has indexed the table by WEIGHT, because weight was the
constraint. Do that here and the table has 10^11 entries, since weights reach
10^9 and there can be 100 items. That is not a slow solution, it is an impossible
one.
Look at the numbers again. The weights are enormous and the VALUES are small: at most
100 each, so at most 10^4 in total.
## Index the table by value
dp[t] = the least total weight of a selection whose value is exactly t
dp[0] = 0, everything else infinity
for each item (w, v):
for t from V down to v:
dp[t] = min(dp[t], dp[t - v] + w)
where V is the sum of all values. The loop runs downward for the usual reason: each
item is used at most once.
The table has V + 1 entries and the whole thing is O(n V), which at these bounds is
10^6.
Swapping which quantity indexes the table and which one is minimised is the move worth remembering. It is available whenever one of the two axes is small, and which axis that is depends only on the constraints.
## Reading the answer
The requirement is value AT LEAST target, not exactly target. So the answer is
min over t >= target of dp[t]
Reading dp[target] alone is wrong whenever no selection hits the target exactly.
(w=9 v=2) (w=8 v=3) (w=7 v=4) with target = 6 answers 15, achieved at value 7 by
taking the second and third items. Value exactly 6 is achievable too, by items 1 and 3,
at weight 16, so reading dp[6] gives 16 and looks perfectly reasonable.
That test exists because the wrong answer here is a valid weight for a valid selection. Nothing about it looks like an error.
## Impossible
If the sum of all values is below target, no selection reaches it and the answer is
-1. That is the only impossible case, since taking everything maximises the value.
## Cost
Weights sum to at most 100 * 10^9 = 10^11, so the table entries need 64 bits even
though the indices are small.