Choose each item at most once
A capacity-five bag has three available items: weight two with value three, weight three with value four, and weight four with value five. Choosing the first two gives total value seven at weight five. Each item may be used once or not at all. Selecting the individually most valuable item gives only five, and value-per-weight greediness does not generally solve the indivisible problem.
The example requires positive integer weights and nonnegative integer capacity, allows integer values and permits choosing nothing. Thus a negative-value item can be skipped and the initial best value is zero. Zero-weight items would require a separately stated variant and are rejected here. Define units, reuse and empty-selection rules rather than assuming the problem name supplies every input contract.
Define subproblems by item prefix and capacity
Let dp[i][c] mean the maximum value using only the first i items with total weight at most c. It does not mean exactly c. Either skip item i and use the previous row at c, or, when its weight w fits, take it and add its value to the previous row at c minus w. Taking the maximum covers both possibilities without reusing the current item.
After the first item, capacities at least two can achieve value three. With the first two items, capacity five achieves seven. Capacity three instead favors value four, and the third item offers value five at capacity four without improving the best value seven at capacity five. Rows change the permitted item set; columns change the weight limit. Trace those meanings before memorizing a recurrence.
| Available items / capacity | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| None | 0 | 0 | 0 | 0 | 0 | 0 |
| Through (2,3) | 0 | 0 | 3 | 3 | 3 | 3 |
| Through (3,4) | 0 | 0 | 3 | 4 | 4 | 7 |
| Through (4,5) | 0 | 0 | 3 | 4 | 5 | 7 |
Recover an actual selection
Start from the final row and requested capacity. If the value equals the preceding row, a valid optimum can skip the current item. Otherwise record that item, subtract its weight and move to the previous row. Equal-value ties choose skipping under this implementation, so it returns one optimum rather than enumerating every optimum.
The included code compares short instances and capacities zero through eight with exhaustive take-or-skip combinations. Returned indices must fit the capacity, and empty input yields zero value with an empty selection. Recomputing the chosen items' value is another useful recovery check: a correct DP total and a correct backtracking path are distinct properties. Preserve the row meaning while reconstructing, since reusing the same row could select an item more than once.
from itertools import product
def knapsack(items,capacity):
if capacity<0 or any(w<=0 for w,v in items):raise ValueError('positive weights required')
dp=[[0]*(capacity+1) for _ in range(len(items)+1)]
for i,(weight,value) in enumerate(items,1):
for c in range(capacity+1):
dp[i][c]=dp[i-1][c]
if weight<=c:dp[i][c]=max(dp[i][c],dp[i-1][c-weight]+value)
chosen=[];c=capacity
for i in range(len(items),0,-1):
if dp[i][c]!=dp[i-1][c]:chosen.append(i-1);c-=items[i-1][0]
return dp[-1][-1],sorted(chosen)
items=[(2,3),(3,4),(4,5)];assert knapsack(items,5)==(7,[0,1])
for count in range(5):
items=[(i+1,(i*3)%7) for i in range(count)]
for capacity in range(9):
reference=max(sum(v*t for (w,v),t in zip(items,mask)) for mask in product([0,1],repeat=count) if sum(w*t for (w,v),t in zip(items,mask))<=capacity)
value,chosen=knapsack(items,capacity);assert value==reference
assert sum(items[i][0] for i in chosen)<=capacity
assert len(chosen)==len(set(chosen))
assert sum(items[i][1] for i in chosen)==value
print('example value=7 items=0,1; brute-force comparisons passed')
Reverse capacity order for a one-row optimization
If only the maximum value is needed, one array can reduce storage to O(W), but update capacities from high to low. Ascending order may read a smaller capacity already updated using the current item and therefore reuse that item. One item of weight two and value three with capacity four exposes the defect: an incorrect ascending update can manufacture value six.
Descending order preserves the previous-stage meaning of the smaller capacity being read. The recurrence's visual similarity does not establish equivalence after storage is overwritten. Recovering item choices from one overwritten row also needs extra information or another method. Choose between the simpler two-dimensional table and a storage-optimized version based on required output, memory limits and how clearly the implementation maintains its stage invariant.
Distinguish numeric capacity from encoded input length
With n items and integer capacity W, the basic table uses O(nW) time and space. That can be practical for modest W and infeasible for a capacity near a billion. W itself can be written in only O(log W) binary bits, so polynomial dependence on its numeric value is not polynomial dependence on the encoded input length. This is why the running time is called pseudopolynomial.
Converting fractional weights to very fine integer units can greatly enlarge the table. Other constraints may favor value-indexed DP, splitting a small item set or approximation. This lesson does not offer one universal solver for every large optimization workload. Its purpose is to make the state definition, one-use transition and dependence on the chosen numeric dimension explicit before selecting a more specialized method.
Recognize a changed problem specification
Unlimited reuse is an unbounded-knapsack variant, while divisible items may support a density-based greedy strategy. A bounded count of several copies per type needs more than the simple take-or-skip choice. Clarify allowed selections before adapting a familiar table. The apparent bug of reusing one item twice can be correct under a different specification.
Requiring exactly the capacity also changes initialization. All-zero initial states would confuse unreachable weights with attainable zero-value choices. An explicit unreachable marker is needed. Here the state means weight at most the capacity. When a requirement changes, update state meaning, base cases, transitions and returned value together. Passing tests for the previous variant is not evidence that a superficially similar recurrence solves the new one.
Also verify distinct recovered indices and that their values sum to the optimal DP value. Fitting the capacity alone does not establish optimal reconstruction.
Recompute the recovered selection’s value
Recompute weight and value from selected indices, checking capacity and equality with the DP optimum. Weight alone would not catch a recovery bug returning an empty list for every instance. Distinct indices also express the0–1 restriction directly.
When several optima tie, asserting one preferred index list can reject another valid answer. Distinguish a displayed example from the full accepted result set. Validate weight, value, uniqueness and the reference optimum instead of adding an unstated tie order. A correct table and correct reconstruction deserve separate checks, and the tests should enforce only the promised contract.
Exercise: solve the take-or-skip comparison
For items of weight/value one/two, three/five and four/six at capacity four, select the first two for value seven. The final item alone gives six, showing why choosing the largest individual value is insufficient. In the final row, compare taking that item for six with skipping it and retaining the previous row's seven.
For one weight-two, value-three item at capacity four, an ascending one-row update writes three at capacity two and then reuses that same-stage value to produce six at capacity four. The valid 0–1 answer is three. Explain that the reference came from the current item stage rather than the previous stage. The loop direction preserves a temporal meaning in the state, not merely a stylistic convention about array traversal.