Variant contracts: bounded budgets, interval cuts and subset routes

This is a supplement to the restored L37–L44 lessons, not a consolidation of them. Their original boolean/counting reductions, grid/string DP, interval and stock-state explanations remain separate subjects. Here the question is what changes when the contract changes. Each program uses finite integer inputs; runtime bounds count arithmetic operations, not arbitrary-precision bit costs.

A bounded number of copies is neither zero-one nor unlimited

An item type has weight w, value v and available count q. Define the state after processing each type as the greatest value achievable at at most each capacity. In the uncompressed recurrence, try taking k copies for every 0 ≤ k ≤ min(q, capacity // w), and read only the previous type's row. This is correct because every feasible multiset has one definite count of the current type. Its cost can be large when counts are large.

Binary grouping turns q identical copies into zero-one bundles. For q=13 the bundles are 1,2,4,6 copies: their total is 13 and every count from 0 through 13 is representable. Inductively, if the current bundles represent every integer from 0 through s, adding a bundle of size at most s+1 extends the interval without a gap. The final remainder satisfies that bound. Do not confuse this with using unlimited bundles, which would violate availability.

def bounded_knapsack(types, capacity):
    """types contains (positive weight, nonnegative value, nonnegative count)."""
    if capacity < 0:
        raise ValueError("negative capacity")
    dp = [0] * (capacity + 1)
    for weight, value, count in types:
        if weight <= 0 or value < 0 or count < 0:
            raise ValueError("invalid item type")
        bundle = 1
        while count:
            take = min(bundle, count)
            w, v = take * weight, take * value
            for c in range(capacity, w - 1, -1):
                dp[c] = max(dp[c], dp[c - w] + v)
            count -= take
            bundle *= 2
    return dp[capacity]
 
assert bounded_knapsack([(2, 3, 2), (3, 5, 1)], 7) == 11
assert bounded_knapsack([(2, 3, 2)], 10) == 6
assert bounded_knapsack([], 0) == 0

Each bundle is processed backward in capacity so it is used once. The cost is O(W times the sum of log(q+1)) transitions and O(W) storage. The budget dependence is pseudopolynomial. In the example, two weight-two copies and one weight-three copy fill capacity seven with value eleven. Unlimited reuse would solve a different problem.

The CP-Algorithms knapsack reference derives zero-one, complete and multiple-knapsack transitions and binary grouping. Its transition order is the external check; exhaustive count enumeration is the independent finite behavioral oracle.

Two budgets mean two capacity axes

For selecting binary strings with a zero budget and a one budget, both resources must fit. A single scalar budget loses information: consuming two zeros is not interchangeable with consuming two ones. Define dp[z][o] as the largest selected count under those two upper bounds. Reverse both capacity loops for each string.

def binary_string_budget(strings, zeros, ones):
    if zeros < 0 or ones < 0 or any(set(s) - {"0", "1"} for s in strings):
        raise ValueError("binary strings and nonnegative budgets required")
    dp = [[0] * (ones + 1) for _ in range(zeros + 1)]
    for s in strings:
        z, o = s.count("0"), s.count("1")
        for a in range(zeros, z - 1, -1):
            for b in range(ones, o - 1, -1):
                dp[a][b] = max(dp[a][b], 1 + dp[a - z][b - o])
    return dp[zeros][ones]
 
assert binary_string_budget(["10", "0001", "111001", "1", "0"], 5, 3) == 4
assert binary_string_budget(["", "0", "1"], 0, 0) == 1

The empty string is permitted by this teaching contract and consumes neither resource, but its item position may still be selected only once. Each state is updated once for that item, adding at most one. This is a useful boundary test rather than a reason to silently exclude empties. Counting string characters costs O(total input characters); transitions cost O(number of strings × zeros × ones), with O(zeros × ones) storage.

Practice: reconstruct selected indices. Use a full item-index table first. Explain why a parent pointer overwritten in a rolled table can accidentally refer to a later item state. A correct witness must fit both budgets and use each original index at most once; matching only the optimum count is insufficient.

Interval cutting: choose the first cut, not a neighboring event

A stick of length L must be cut at specified interior positions. Each cut costs the length of the current piece. Let dp[i][j] be the minimum cost to complete cuts strictly between sorted boundaries points[i] and points[j]. If k is the first cut in this interval, its immediate cost is points[j]-points[i], and subsequent left/right pieces are independent. This differs from Burst Balloons, where choosing the last balloon keeps its final neighbors fixed. The dependency structure, not a slogan about first or last, chooses the right direction.

def minimum_cut_cost(length, cuts):
    if length < 0 or any(not 0 < c < length for c in cuts):
        raise ValueError("cuts must be strictly interior")
    points = [0] + sorted(set(cuts)) + [length]
    n = len(points)
    dp = [[0] * n for _ in range(n)]
    choice = {}
    for span in range(2, n):
        for i in range(n - span):
            j = i + span
            value, k = min((dp[i][k] + dp[k][j] + points[j] - points[i], k)
                           for k in range(i + 1, j))
            dp[i][j] = value
            choice[i, j] = k
    order = []
    pending = [(0, n - 1)]
    while pending:
        i, j = pending.pop()
        if (i, j) in choice:
            k = choice[i, j]
            order.append(points[k])
            pending.extend([(k, j), (i, k)])
    return dp[0][-1], order
 
assert minimum_cut_cost(7, [1, 3, 4, 5])[0] == 16
assert minimum_cut_cost(7, []) == (0, [])

Every legal schedule has a first cut, so the recurrence considers its branch; induction on the number of interior cuts proves optimality. The returned preorder is a legal execution order, not just a sorted cut list. Repeated input coordinates are treated as one required cut. For m distinct cuts, time is O(m³), table storage O(m²), and the returned witness uses O(m) space. Verify it independently by maintaining current segment boundaries and charging the length of the containing segment for each cut.

A subset alone is insufficient for a route

In assignment DP, the subset can determine the next worker index by popcount. In a traveling-salesperson route, the next edge also depends on the last vertex. Two paths visiting the same set but ending at different vertices can have different future costs. Define dp[mask][last] as the cheapest path starting at zero, visiting exactly mask, ending at last. Close the cycle only after all vertices have been visited.

def held_karp(cost):
    """Complete square directed cost matrix, finite numbers; start/end at vertex zero."""
    n = len(cost)
    if any(len(row) != n for row in cost):
        raise ValueError("square matrix required")
    if n <= 1:
        return 0
    inf = float("inf")
    dp = [[inf] * n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for last in range(n):
            if dp[mask][last] == inf:
                continue
            for nxt in range(1, n):
                if not mask & (1 << nxt):
                    new = mask | (1 << nxt)
                    dp[new][nxt] = min(dp[new][nxt], dp[mask][last] + cost[last][nxt])
    return min(dp[-1][last] + cost[last][0] for last in range(1, n))
 
assert held_karp([[0, 2, 9], [1, 0, 3], [4, 8, 0]]) == 9
assert held_karp([]) == held_karp([[7]]) == 0

The empty/single-vertex tour convention charges no self-edge. Negative finite costs are allowed because every transition adds a previously absent vertex: the state graph is acyclic, and the tour cannot repeatedly exploit a negative cycle. This is not unrestricted shortest-path search. There are O(n2ⁿ) states, each trying O(n) successors, so O(n²2ⁿ) transitions and O(n2ⁿ) storage. A Python table with millions of references is already substantial; bitmasks do not make exponential space disappear.

For n≤7, enumerate every permutation of vertices 1 through n−1 and sum the actual closed-route edges. This oracle reasons in complete routes rather than copying the DP recurrence. The CP-Algorithms DP introduction supplies the reusable-state method; the explicit route-state derivation above and independent permutation tests are the evidence for this implementation.

Transfer assessment

1. Change bounded knapsack to require exact weight. Explain why zero-initializing every capacity now lies about reachability. Use an unreachable sentinel except at capacity zero.
2. Return a minimum-cut witness and simulate it. Two schedules may tie; compare cost and validity, not only list order.
3. Remove the last dimension from Held–Karp and produce two partial paths with the same mask and different completion costs. That counterexample demonstrates state insufficiency.
4. Add prerequisites between selected items. Do not assume the capacity state still suffices: legality can depend on which items, not only their aggregate cost.

The repository verifier executes these exact fences and bounded independent oracles. Passing those finite cases is not a universal proof or a maximum-constraint benchmark; the inductive arguments and explicit input contracts remain necessary.

Corrective source notes

• Knapsack Problem - Algorithms for Competitive Programming — Zero-one knapsack row compression scans capacity downward so the dependency still refers to the previous item row. Checked 2026-10-07.
• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.
• Enumerating submasks of a bitmask - Algorithms for Competitive Programming — A mask encodes a subset by bit membership; this does not eliminate exponential subset counts. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.