Python 0/1 knapsack: descending capacity prevents item reuse

Operation contract

The cargo fixture accepts positive integer weights and nonnegative integer values. It visits capacities from high to low for each item, so the lower-capacity state still belongs to the previous item set. Ascending capacity would let the current item feed its own later updates and change the problem into a reusable-item recurrence.

Failure and ownership boundary

The function caps capacity at 256 and item count at 32, rejects bool and returns only the optimum value. It does not identify a selected load or model fractional cargo. The zero-capacity and empty-item results are valid zero values, distinct from a parser failure. Python memoization: cache bounded states without hiding recursion depth deliberately solves another recurrence.

Working program

def cargo_value(items, capacity):
    if type(capacity) is not int or not 0 <= capacity <= 256 or len(items) > 32:
        raise ValueError("cargo budget")
    if any(type(weight) is not int or type(value) is not int or weight <= 0 or value < 0 for weight, value in items):
        raise ValueError("positive weight and nonnegative value required")
    best = [0] * (capacity + 1)
    for weight, value in items:
        for available in range(capacity, weight - 1, -1):
            best[available] = max(best[available], best[available - weight] + value)
    return best[capacity]

print(cargo_value([(2, 6), (3, 8), (4, 9)], 5))
print(cargo_value([(2, 6)], 4))

Output

14
6

Costs and limits

Time is O(n*C) and storage O(C) for capacity C and n items, aside from integer digit costs. This is pseudo-polynomial in numeric capacity, not polynomial in the length of its textual encoding.

Common Mistakes

• Ascending updates would allow the same item more than once.
• Do not advertise a selected-item list when returning only its total value.

Connected lessons

Python memoization: cache bounded states without hiding recursion depth, Python longest common subsequence: rolling-row DP and its limits, Python input exercise: accept an explicit integer grammar.

Follow the ownership and update boundary

Python weighted interval scheduling: reconstruct the accepted nonoverlapping jobs.