42. Max-Value Allocation of Compute-Hours

Problem

A research team has a fixed pool of GPU compute-hours for the week and a backlog of candidate experiments, each an all-or-nothing run with a known cost in compute-hours and an expected research value if it's run. The team wants to choose which experiments to run within the compute-hour budget to maximize total expected value.

Given the experiments as (cost_hours, expected_value) pairs, each runnable at most once, return the maximum total expected_value achievable without the summed cost_hours exceeding budget_hours. This must run in O(n * budget_hours) time using dynamic programming, not brute-force enumeration of all subsets.

Source: src/42_max_value_compute_hour_allocation.py

def max_value_allocation(experiments: list[tuple[int, int]], budget_hours: int) -> int:
    ...

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

>>> max_value_allocation([(10, 60), (20, 100), (30, 120)], 50)
220

Step-by-Step Approach

1. Recognize the shape: each experiment is all-or-nothing (can't run 60% of an experiment for 60% of its value), a fixed budget, and a maximize-value objective — the classic 0/1 knapsack.
2. Define dp[b] as the best total value achievable using a budget of exactly b hours or less, considering only the experiments processed so far.
3. Initialize dp as an array of zeros of length budget_hours + 1 — with no experiments considered yet, every budget level achieves zero value.
4. Process experiments one at a time. For each experiment, decide, for every possible remaining budget, whether including this experiment beats excluding it: dp[b] = max(dp[b], dp[b - cost] + value).
5. Iterate the budget dimension from high to low (not low to high) within each experiment's update. This ensures each experiment's own contribution to dp[b - cost] hasn't already been baked in during this same pass, which would let it be "reused" more than once.
6. After processing every experiment, dp[budget_hours] holds the answer: the best achievable value using up to the full budget.

The key insight is that iterating the budget backward within each experiment's pass is what turns a 2D DP table (experiments x budget) into a single rolling 1D array without corrupting the "used at most once per experiment" constraint.

Reference solution

def max_value_allocation(experiments: list[tuple[int, int]], budget_hours: int) -> int:
    # 0/1 knapsack, rolling 1D dp array iterated budget-descending per item,
    # O(n * budget_hours) time, O(budget_hours) space. Descending iteration
    # ensures each experiment is only ever counted once per row update.
    dp = [0] * (budget_hours + 1)
    for cost_hours, value in experiments:
        for remaining in range(budget_hours, cost_hours - 1, -1):
            dp[remaining] = max(dp[remaining], dp[remaining - cost_hours] + value)
    return dp[budget_hours]

Key Functions & Tricks

• dp = [0] * (budget_hours + 1) — one rolling array indexed by remaining budget, reused across all experiments
• Descending budget iteration — the single trick that lets a 1D array simulate the 2D 0/1 knapsack table without an experiment being applied twice in the same pass
• range(budget_hours, cost_hours - 1, -1) — skips budgets too small to afford the current experiment, since dp[remaining] is already correct (unchanged) for those
• dp[remaining - cost_hours] + value — the "include this experiment" branch, built on the best value achievable with the leftover budget
• max(dp[remaining], ...) — the "exclude this experiment" branch is simply dp[remaining]'s value from before this experiment was considered

How to Recognize This Pattern