Fill the Bag Exactly
Each item has a weight and a value, and may be used at most once. Print the largest
total value of a selection whose weight is EXACTLY C, or -1 if no selection weighs
exactly C.
items (w=2 v=3) (w=3 v=4) (w=4 v=6), C = 7 -> 10
items (w=2 v=3) (w=4 v=6), C = 5 -> -1
Problem #236 asks for weight AT MOST C, and the two differ by one line: how the table
is initialised.
## The initialisation is the problem
at most C dp[t] = 0 for every t 0 means "an empty selection weighs t or less"
exactly C dp[0] = 0, everything else -infinity
In the at-most version, dp[t] = 0 is a true statement for every t: the empty
selection has value 0 and weight 0, which is at most t. So every entry starts valid.
In the exact version, dp[t] = 0 would claim a selection of weight exactly t and
value 0 exists, which is false for every t above 0. Only dp[0] is genuinely
reachable at the start, and the rest must be marked UNREACHABLE.
Negative infinity is what carries "no selection has this weight" through the recurrence. Once the table is initialised correctly the loop is unchanged:
for each item (w, v):
for t from C down to w:
if dp[t - w] is reachable:
dp[t] = max(dp[t], dp[t - w] + v)
## The guard on the read
dp[t - w] + v must only be computed when dp[t - w] is reachable. Skip the guard and
in C, C++ or Java the sentinel plus a value can overflow to something large and positive,
at which point an unreachable weight looks like the best answer.
Use a sentinel far from the type's limit, or test for it explicitly. Both work; not thinking about it does not.
## Reading the answer
dp[C] if it is reachable, otherwise -1. Unlike the at-most version there is no
scanning for a maximum, because the weight is pinned.
## Two boundaries that matter
C = 0 answers 0. The empty selection weighs exactly 0 and has value 0, so the answer is
0 and not -1. That test is in the bank because the natural reading of "must weigh
exactly 0" as "impossible" is wrong.
(w=5 v=2) (w=5 v=3) with C = 5 answers 3. Two items of the same weight where only
one fits, so the better one must be chosen, and a solution that stops at the first
reachable combination answers 2.
(w=4 v=10) (w=2 v=1) (w=2 v=1) with C = 4 answers 10. Two different selections weigh
exactly 4, and the heavier-valued one uses fewer items, so any rule based on item count
gets it wrong.