48. Max-Value Agent-Hour Allocation

Problem

A support org has a fixed number of agent-hours available this week and a list of ticket TYPES it could staff up to fully resolve. Each ticket type costs a certain number of agent-hours and, if fully staffed, yields a certain business value (e.g. churn prevented, expansion revenue protected).

Each type is all-or-nothing: it either gets fully staffed or not at all, it can't be partially resolved. Choose a subset of ticket types that fits within the agent-hour budget and maximizes total resolved value — this is the classic 0/1 knapsack problem.

Source: src/48_max_value_agent_hour_allocation.py

def max_value_allocation(items: list[tuple[int, int]], budget: int) -> int:
    # items is a list of (cost_hours, value) pairs

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

>>> max_value_allocation(items=[(5, 10)], budget=5)
10

Step-by-Step Approach

1. Define dp[b] as the maximum value achievable using exactly a budget of at most b agent-hours, over the items considered so far.
2. Initialize a 1D array dp of size budget + 1, all zeros (with zero items chosen, zero value at any budget).
3. For each item (cost_hours, value), decide whether including it improves dp[b] for each b >= cost_hours: candidate value is dp[b - cost_hours] + value.
4. Iterate the budget dimension descending (from budget down to cost_hours) when updating in place — this ensures each item is only used once (0/1, not unbounded knapsack), since a descending pass never reads an already-updated cell for the same item.
5. After processing all items, dp[budget] holds the maximum total value achievable within the full budget.

The key insight is the direction of the inner loop: iterating the budget dimension backwards when reusing a single 1D array is what turns an unbounded knapsack (each item usable any number of times) into a 0/1 knapsack (each item usable at most once), without needing a full 2D items x budget table.

Reference solution

def max_value_allocation(items: list[tuple[int, int]], budget: int) -> int:
    # 0/1 knapsack, rolling 1D dp array iterated budget-descending per item, O(n*budget) time/O(budget) space
    # rolling 1D array, collapses the 2D dp[item][budget] table
    dp = [0] * (budget + 1)
    for cost_hours, value in items:
        # descending: each item used at most once
        for remaining in range(budget, cost_hours - 1, -1):
            # skip vs take item
            dp[remaining] = max(dp[remaining], dp[remaining - cost_hours] + value)
    return dp[budget]

Key Functions & Tricks

• range(budget, cost_hours - 1, -1) — negative-step range, iterates the budget dimension high to low.
• max(dp[remaining], dp[remaining - cost_hours] + value) — best of skipping this item vs. taking it.
• Rolling 1D array instead of a 2D DP table — cuts space from O(n*budget) to O(budget).
• Descending inner loop (the key trick) — ensures each item is used at most once, i.e. 0/1 not unbounded knapsack.
• [0] * (budget + 1) — list-multiplication idiom to preallocate a fixed-size numeric array.

How to Recognize This Pattern