Dynamic Programming for Resource Allocation

You have four units of something scarce — millions of pounds of capital, servers, sales staff, hours — and three projects that could each use them. Every project turns resource into return, but with diminishing effect: the first unit does the most good, the second a little less, and so on. How do you split the four units to earn the most in total? There are only fifteen ways here, but with twenty projects and a hundred units the choices run into the billions. Dynamic programming solves the whole family in one tidy sweep — and the trick is to make the resource remaining the state.

The separable structure

Resource-allocation problems have a special shape that DP loves. Let x_i \ge 0 be the whole units given to project i, and r_i(x_i) the return it yields. We want

\max\; \sum_{i=1}^{N} r_i(x_i) \quad\text{subject to}\quad \sum_{i=1}^{N} x_i = B,\;\; x_i \ge 0 \text{ integer.}

The objective is separable — a sum of per-project terms — and the only thing tying the projects together is the shared budget B. That is exactly the ingredient DP needs: we can commit resource to one project at a time, carrying forward only how much budget is left. It is the same additive structure that makes the knapsack problem yield to dynamic programming.

The DP formulation

Treat each project as a stage. The state is the amount of budget s still available when we reach that stage, and the decision is how many units x to hand this project. Writing f_i(s) for the best total return obtainable from projects i, i+1, \dots, N when s units remain, the Bellman relation is

f_i(s) = \max_{0 \le x \le s}\;\bigl\{\, r_i(x) + f_{i+1}(s - x) \,\bigr\}, \qquad f_{N+1}(s) = 0.

Choose an amount for project i, collect its return, and add the best you can do with the leftover on the remaining projects. Solve backwards from the last project and the answer falls out.

Worked example: four units, three projects

Here are the return tables. Notice each column climbs but flattens — diminishing returns.

units x	r_1(x)	r_2(x)	r_3(x)
0	0	0	0
1	5	4	3
2	9	7	6
3	11	11	9
4	12	13	12

Stage 3 (project 3 alone). With s left, give it all away: f_3(s) = r_3(s), so f_3 = (0,3,6,9,12) for s = 0,\dots,4.

Stage 2. Apply f_2(s) = \max_x\{ r_2(x) + f_3(s-x) \}. For example f_2(4) = \max(0{+}12,\,4{+}9,\,7{+}6,\,11{+}3,\,13{+}0) = 14, best at x_2 = 3. The full row is f_2 = (0,4,7,11,14).

Stage 1. Only the full budget matters: f_1(4) = \max_x\{ r_1(x) + f_2(4-x) \}:

x_1	r_1(x_1)	f_2(4-x_1)	total
0	0	14	14
1	5	11	16
2	9	7	16
3	11	4	15
4	12	0	12

The optimum is f_1(4) = 16. Tracing the choices back, one optimal allocation is (x_1, x_2, x_3) = (1, 3, 0): return 5 + 11 + 0 = 16. (There is a tie — (2,1,1) and (2,2,0) also score 16 — a reminder that optima need not be unique.)

Diminishing returns, seen

The reason spreading the budget can beat piling it into one project is the curve below: each project's return bends over as it is fed more. When a project's marginal gain has fallen below what another project would give for the same unit, you switch — and DP does this bookkeeping automatically.

Very nearly. The knapsack problem is the special case where each project ("item") can take only zero or one unit, and the resource is the knapsack's weight capacity. General resource allocation lets a project absorb many units with its own diminishing return schedule. Both are solved by the identical DP skeleton — stages over the items, state equal to the capacity remaining, a max over how much to commit. Recognising that a new problem is "knapsack-shaped" instantly hands you a solution method, which is why the pattern is worth memorising.

DP shines when the state is a single small number — here, budget remaining. But suppose the resource were three-dimensional: money, staff, and machine time, each with its own budget. The state becomes a triple (s_1, s_2, s_3), and the number of states to tabulate is the product of the three ranges. Add a fourth resource and it multiplies again. Bellman himself named this the curse of dimensionality: the state space grows exponentially in the number of state variables, and the tidy table becomes impossibly large. DP is a scalpel for problems that separate into stages with a low-dimensional state — not a universal solvent.