Dinesh/ Blog
algorithms

Variant contracts: bounded budgets, interval cuts and subset routes

Extend the restored problem-family series with bounded knapsack, two resource budgets, interval reconstruction and Held–Karp routes, using independent tiny oracles.

30 min read
Checking device speech…
Lesson preparation & details

Level: advanced

By the end, you should be able to

  • Derive a state that distinguishes resource and history constraints
  • Prove dependency order before compressing storage
  • Validate tiny optimization instances by exhaustive enumeration

Bring with you

Sources checked: . A source check does not change the publication or update date.

Editorial review: · What review means

In this article · 6 sections

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); the transition bound is O(number of strings × (zeros + 1) × (ones + 1)), with O((zeros + 1) × (ones + 1)) storage. The extra one on each axis includes the zero-budget states: those states still exist and can select empty strings. Supply a reusable finite sequence of strings; the validation pass and the selection pass both traverse it.

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

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.

Pause / Recall / Apply

Can you explain it without the page?

Close the example. Reconstruct the core idea, then change one assumption. Mark complete when you’re ready; you can always undo it.

Stored in this browser only. No account, no sync. Clearing browser data removes your record.