01 / The idea
The highest-value-per-megabyte item can block the best pair.
Handbook is worth 31 points in 6 MB, a strong density. Diagrams adds 17 points in 4 MB, so a greedy policy reaches 48 points exactly at the limit.
0/1 knapsack maximizes total value without exceeding a capacity when every item is one-time and indivisible. The two five-megabyte downloads each score 25, so together they beat the attractive ratio.
The question is not “which item looks best now?” It is “what is the best value available for each remaining capacity after the items seen so far?”
Keep the best bundle, not the best-looking item.
selected subset available item
Set a budget and a value.
Each offline item has a size and a reader-value score. The 10 MB budget can hold some items, but every item may be downloaded at most once.
Reduced motion: choose a scene to see its completed state.
Read this scene
Each offline item has a size and a reader-value score. The 10 MB budget can hold some items, but every item may be downloaded at most once.
The 10 MB capacity and five one-time items are ready. No subset has been chosen.
Watch and Step through replay the budget story. Try it changes the capacity and runs the same take-or-skip implementation.
Step through the shortcut, then watch the table backtrack from 10 MB. The result changes the bundle, not just the score: both selected items are five megabytes, so neither can coexist with Handbook.
02 / Name the rule
Every cell compares taking the item with leaving it out.
Let dp[i][c] be the best value using the first i items and at most
capacity c. If item i does not fit, the answer is the row above. If
it fits, choose the better of the two legal futures:
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - size] + value)
The reference row is i - 1 in both branches. That is the one-time guarantee: taking
an item cannot accidentally take it again.
Keep the earlier best
Leave this item out and carry the best value already found for the same capacity.
Spend its size once
Add the item’s value to the best earlier bundle that fits in the remaining capacity.
Recover the identities
Walk from the last cell upward; a changed value means the current item was selected.
Why density is not a proofA ratio orders items, not bundles
Value per megabyte works for fractional knapsack, where an item can be split. In the 0/1 version, the leftover capacity after a local choice can be too small for a valuable combination. The table compares combinations directly, so it can certify the best value for every capacity.
03 / Read the shape
The table is the algorithm’s memory.
Basic form is solveKnapsack: it fills the take-or-skip value
table and backtracks it to recover the selected IDs. In the wild adds the
types, input validation, totals, and the value-density baseline. At the call site compares the dynamic result with a density baseline so the tradeoff
is visible.
solveKnapsack: fill a take-or-skip table for each item and each integer capacity, then walk up the rows to recover the selected items.
export function solveKnapsack(problem: KnapsackProblem): KnapsackResult {
validate(problem);
const { capacity, items } = problem;
const table = Array.from({ length: items.length + 1 }, () => Array<number>(capacity + 1).fill(0));
const snapshots: KnapsackSnapshot[] = [];
for (let row = 1; row <= items.length; row += 1) {
const item = items[row - 1];
for (let available = 0; available <= capacity; available += 1) {
const skip = table[row - 1][available];
const take =
item.size <= available
? table[row - 1][available - item.size] + item.value
: Number.NEGATIVE_INFINITY;
table[row][available] = Math.max(skip, take);
}
const selectedIds = selectedIdsFromTable(table, items, row, capacity);
snapshots.push({
item: item.id,
row,
bestValue: table[row][capacity],
selectedIds,
table: cloneTable(table.slice(0, row + 1))
});
}
const selectedIds = selectedIdsFromTable(table, items, items.length, capacity);
return {
...summaryFromIds(problem, selectedIds),
table: cloneTable(table),
snapshots
};
}
function selectedIdsFromTable(
table: number[][],
items: KnapsackItem[],
row: number,
capacity: number
): string[] {
const selected: string[] = [];
let remaining = capacity;
for (let index = row; index > 0; index -= 1) {
if (table[index][remaining] !== table[index - 1][remaining]) {
const item = items[index - 1];
selected.push(item.id);
remaining -= item.size;
}
}
return selected.reverse();
}func solveKnapsack(problem KnapsackProblem) (KnapsackResult, error) {
if err := validate(problem); err != nil {
return KnapsackResult{}, err
}
table := make([][]int, len(problem.Items)+1)
for i := range table {
table[i] = make([]int, problem.Capacity+1)
}
snapshots := make([]KnapsackSnapshot, 0, len(problem.Items))
for row := 1; row <= len(problem.Items); row++ {
item := problem.Items[row-1]
for available := 0; available <= problem.Capacity; available++ {
skip := table[row-1][available]
take := -1
if item.Size <= available {
take = table[row-1][available-item.Size] + item.Value
}
if take > skip {
table[row][available] = take
} else {
table[row][available] = skip
}
}
selectedIDs := selectedIDsFromTable(table, problem.Items, row, problem.Capacity)
snapshots = append(snapshots, KnapsackSnapshot{
Item: item.ID,
Row: row,
BestValue: table[row][problem.Capacity],
SelectedIDs: selectedIDs,
Table: cloneTable(table[:row+1]),
})
}
selectedIDs := selectedIDsFromTable(table, problem.Items, len(problem.Items), problem.Capacity)
return KnapsackResult{
KnapsackSummary: summaryFromIDs(problem, selectedIDs),
Table: cloneTable(table),
Snapshots: snapshots,
}, nil
}
func selectedIDsFromTable(table [][]int, items []KnapsackItem, row, capacity int) []string {
selected := make([]string, 0)
remaining := capacity
for index := row; index > 0; index-- {
if table[index][remaining] != table[index-1][remaining] {
item := items[index-1]
selected = append(selected, item.ID)
remaining -= item.Size
}
}
for left, right := 0, len(selected)-1; left < right; left, right = left+1, right-1 {
selected[left], selected[right] = selected[right], selected[left]
}
return selected
}Reading the TypeScriptRows, capacities, and reconstruction
table[row][capacity] stores the best value after one more item. The reconstruction
loop compares adjacent rows and pushes an ID only when taking the item improved the cell.
Reading the GoThe same integer contract
Go uses the same row-by-row recurrence and returns the same per-row snapshots (the film on this page replays the TypeScript ones). Both programs print the same selected IDs, total size, and total value.
What is refusedKeep the state finite
Both examples require integer capacities and positive item sizes, cap the input dimensions, and reject duplicate lowercase IDs. Negative values or fractional sizes need a different contract and recurrence.
04 / Try a decision
What must each cell compare?
A ratio shortcut gives a useful comparison, but it cannot enforce the one-time choice or see future combinations. Choose the invariant that makes the recurrence correct.
05 / Follow the cost
Pay for every item-capacity decision.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Validate the budget and items | O(n) | O(1) | Read each size and value once and reject malformed or oversized inputs. |
| Fill the 0/1 table | O(n²C) as shown | O(n²C) as shown | For n items and integer capacity C, comparing skip and take at every cell is O(nC) time and space. The shown code also copies the table so far and backtracks after every row for the film, which makes it O(n²C); without those snapshots it is O(nC). |
| Recover the selected subset | O(n) | O(n) | Start at the last row and full capacity and walk up the rows; a changed value marks a selected item and spends its size. Then reverse the identities. |
| Compress the table | O(nC) | O(C) | A one-row value table is possible when reconstruction is stored separately or not needed. |
With n items and integer capacity C, filling the full table takes
O(nC) time and space. The version shown also copies the table so far after every row so the
film can replay it, which costs O(n²C); drop those snapshots in production. The table itself
is pseudo-polynomial: doubling the numeric capacity doubles the work even when the input’s
written length grows much more slowly.
A one-dimensional table reduces extra space to O(C), but it must be filled from high capacity to low capacity. That descending order is what prevents the current item from being reused in the same pass.
06 / Give it a real job
Plan the downloads before the reader goes offline.
The reader app’s sync step knows how much storage is left and has a list of downloads, each
with a size from the server and a score from what the reader tends to open. Before the
device goes offline, it calls solveKnapsack with that budget and list, then queues
the selected IDs for download.
The solver owns one decision: which bundle fits and scores highest. It doesn’t own the scores, which come from reading history, and it doesn’t download anything or retry a failed file. Real files aren’t whole megabytes, and the table needs whole numbers, so the sync step rounds every size up. Rounding up never lets a bundle overflow the budget; counting in smaller units, such as 100 KB, is more exact but makes the table about ten times wider.
This runs in the app’s background sync, not in a component: the downloads screen only shows the bundle it gets back.
07 / Make the call
Match the recurrence to the item rules.
Use 0/1 knapsack when each item is either included once or left out, values are additive, and there is one bounded capacity. It fits download bundles, cargo selection, and a small set of projects competing for a budget.
Use Huffman coding when the goal is to minimize a weighted code length, not select a subset. Use Hungarian assignment when every row and column must receive exactly one match.
Three variants to recognizeSame word, different rules
- Fractional: split an item; value density becomes a valid greedy strategy.
- Unbounded: reuse an item; the recurrence may read the current row or iterate capacity upward.
- Multiple constraints: add a state dimension, often paying O(nC₁C₂) or more.
08 / Take the idea with you
Explain the download plan without saying “knapsack.”
“Make a table with one row per download and one column per megabyte of room. Each cell holds the best score you can get from the downloads so far in that much room: either skip this download and keep the cell above, or take it once and add its score to the cell above that leaves room for it. The last cell is the best score, and walking back up the rows tells you which downloads made it.”
Before moving on, think of a budget you fill with one-time choices, such as a carry-on bag or a sprint’s hours. Name the item with the best value for its size, and check whether two smaller ones would beat it.
Connections to follow nextRelated lessons
- Dynamic programming is the general idea: name the state, write the choice, and fill a table of answers to smaller questions.
- Weighted interval scheduling uses the same take-or-skip choice, with time overlap instead of room.
- Divide and conquer, greedy choices, and backtracking shows when a greedy choice is safe; the value-per-megabyte shortcut here is a greedy choice that isn’t.