Each edge has three allowed \((\text{integer weight},\text{cost})\) options:
There are exactly \(3^3=27\) full assignments. The table stores the minimum cost at each exact weight; columns zero through eight are displayed.
Reading the drawing
Columns are exact integer weights and rows are successive numbers of processed edges. Each cell gives the minimum declared cost at that exact weight; infinity marks an unreachable state. The budget optimum is the minimum across the allowed columns.
Drawing labels and data 50 labels
Read the original labels as selectable text. Tables preserve grid relationships; other short labels are grouped compactly.
| Row / column | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| edges 0 | 0 | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) |
| edges 1 | 7 | \(\infty\) | 3 | \(\infty\) | 1 | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) |
| edges 2 | 13 | 11 | 9 | 7 | 7 | 4 | \(\infty\) | 2 | \(\infty\) |
| edges 3 | 22 | 20 | 18 | 16 | 14 | 12 | 12 | 9 | 8 |
Columns are exact weights; the budget optimum is the minimum across allowed columns.
Read the final row correctly
At budget four, minimize across columns zero through four. The optimum costs 14: choose weights \((2,0,2)\) with costs \((3,6,5)\). The zero-weight choice on edge two is its first, more expensive option. A locally cheap choice can consume too much of the shared budget.
The checker compares the recurrence with complete enumeration for every budget from zero through twelve. Infeasible states remain \(+\infty\); they are not zero-cost states.
Quantization must be conservative
Suppose real errors are \(3/50\) and \(2/25\), and one integer unit represents \(1/10\). Rounding down gives two zero weights, even though the true sum is \(7/50>1/10\). Rounding up gives a certified upper envelope instead. The budget method is exact for its integers; it cannot repair unsafe integers supplied by a preprocessing step.
Read this as
The table optimizes the declared option set exactly. Accuracy depends separately on the validity and conservativeness of the option weights.