Progress and remaining capacity are different information

Picture

You have a bag with limited capacity and items you may each take once. Remaining capacity tells you what fits. The next item index tells you what is still available. Losing either coordinate can merge questions whose answers differ.

Predict

Two states both have capacity 4. One can still choose a weight-4, value-100 item; the other has already passed it. Can their best remaining values share a cache entry keyed only by 4?

Reveal the reasoning

No. The available item set changes the remaining optimum. Using an index to define a fixed suffix of available items avoids storing a whole set.

Go deeper: single use is encoded in both branches

Items are (weight, value) pairs, weights are positive integers, and capacity is a nonnegative integer. Picking no items is allowed. best(i, room) means maximum value using items i onward within room.

from functools import cache

def pack(items, capacity):
    @cache
    def best(i, room):
        if i == len(items):
            return 0
        weight, value = items[i]
        answer = best(i + 1, room)
        if weight <= room:
            answer = max(answer, value + best(i + 1, room - weight))
        return answer
    return best(0, capacity)

assert pack([(2, 3), (3, 4), (4, 5)], 5) == 7
assert pack([(2, 3)], 4) == 3
assert pack([], 5) == 0

Both skip and take advance to i+1; that is why an item cannot be reused. If the take branch stayed at i, it would describe unlimited reuse under suitable conditions. The code’s small index change expresses a major rule change.

There are at most (n+1)(W+1) states and constant work per state: O(nW) time and cache space, with O(n) stack depth. This is pseudo-polynomial in numeric capacity W. A huge capacity can make the method infeasible even when there are few items.

To reconstruct chosen items, follow decisions consistent with the cached optimum; storing only the value is not the same as emitting the selection.

Analogy limit: the bag story is incidental. Choosing projects under a budget or selecting questions under a time limit can have the same structure when the same single-use and additive assumptions hold.

Change one rule

You must fill capacity exactly. Is zero still the correct answer for every state with no items left?

Check the variation

No. Only zero remaining capacity is a feasible exact fill. Positive remaining capacity must be marked impossible, such as with negative infinity for maximization. Otherwise the recurrence silently allows underfilling.

Connect

Budget DP adds resource information to a location. Compression explains descending capacity updates. Greedy tests whether sorting by an attractive item score is justified.