48. Max-Value Allocation of GPU-Hours Across Models

Problem

A team running SSM-based models has a fixed GPU-hour budget for the current cycle and a shortlist of candidate model runs. Each candidate costs some number of GPU-hours and yields some expected value (e.g. a quality-improvement score). Each candidate can be funded at most once.

Choose the subset of candidates that maximizes total value without the summed cost exceeding the budget. models is a list of (gpu_hours_cost, value) pairs.

Source: src/48_max_value_gpu_hour_allocation.py

def max_value_allocation(models: list[tuple[int, int]], budget: int) -> int:

>>> max_value_allocation([(2, 3), (3, 4), (4, 5), (5, 6)], 5)
7

>>> max_value_allocation([(1, 1), (2, 2), (3, 3)], 0)
0

Step-by-Step Approach

1. Recognize the classic 0/1 knapsack shape: a set of items each with a cost and a value, a fixed capacity, and each item usable at most once — that "at most once" constraint is what makes it 0/1 rather than unbounded knapsack.
2. Define dp[b] as the best total value achievable using a budget of at most b GPU-hours, considering only the models processed so far.
3. Process models one at a time. For each model with (cost, value), every budget level b >= cost can potentially improve by taking that model: dp[b] = max(dp[b], dp[b - cost] + value).
4. Iterate the budget axis downward (from budget to cost) when updating for a given model. This is the detail that enforces "used at most once" — a forward pass would let dp[b - cost] already reflect this same model having been added, effectively reusing it.
5. After processing every model, dp[budget] holds the answer: the best total value achievable within the full budget.
6. Handle the trivial cases: an empty model list or a budget of 0 both leave dp all zeros, so the answer is 0.

The key insight is the direction of the inner loop: walking the budget axis downward, not upward, is what turns the same one-dimensional recurrence used for unbounded knapsack into the "each item once" version, without needing a full 2D dp[item][budget] table.

Reference solution

def max_value_allocation(models: list[tuple[int, int]], budget: int) -> int:
    # dp[b] = best achievable value using at most b GPU-hours so far
    dp = [0] * (budget + 1)
    for cost, value in models:
        # walk the budget axis downward so each model is only counted once
        # (0/1 knapsack) -- a forward pass would let the same model be
        # "reused" within one iteration
        for b in range(budget, cost - 1, -1):
            dp[b] = max(dp[b], dp[b - cost] + value)
    return dp[budget]

Key Functions & Tricks

• dp[b] (1D array) — collapses what could be a 2D dp[item][budget] table into O(budget) space by processing items one at a time.
• Downward budget iteration (range(budget, cost - 1, -1)) — the single trick that enforces "each model used at most once" in a 1D table.
• dp[b] = max(dp[b], dp[b - cost] + value) — the core knapsack recurrence: either skip this model (keep dp[b]) or take it (add its value to the best solution for the remaining budget).
• O(n × budget) time, O(budget) space — pseudo-polynomial, since it depends on the numeric size of budget, not just the item count.

How to Recognize This Pattern