491. 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.

Constraints - `1 ≤ n ≤ 1000` - `0 ≤ C ≤ 10000` - `1 ≤ weight ≤ 10000` - `1 ≤ value ≤ 1000000`