Step 6 of 6
The knapsack problem
You're packing for a hike. Each item has a weight and a value, your backpack holds at most capacity, and each item can be taken once or not at all. Which items give the most value? This is the 0/1 knapsack problem, and it shows up at work as budget allocation, choosing which features fit in a release, or picking ads for a time slot.
Greedy fails. "Take the best value per kilo first" sounds right: with capacity 10 and items tent (6 kg, 30), stove (5 kg, 20) and camera (5 kg, 20), the tent has the best ratio (5 per kilo), but after taking it nothing else fits: 30. The stove and camera together give 40.
Brute force tries all 2ⁿ subsets. DP does better. State: best[i][w] = the most value using only the first i items with capacity w. For item i - 1 (with weight wt and value val), either skip it, or (if it fits) take it and add its value to the best you could do with the remaining capacity:
best[i][w] = max(best[i - 1][w], best[i - 1][w - wt] + val)
fn knapsack(items: &[(&str, usize, u32)], capacity: usize) -> u32 {
let n = items.len();
// best[i][w] = the most value using only the first i items with capacity w
let mut best = vec![vec![0u32; capacity + 1]; n + 1];
for i in 1..=n {
let (_, weight, value) = items[i - 1];
for w in 0..=capacity {
best[i][w] = best[i - 1][w]; // skip item i - 1
if weight <= w {
best[i][w] = best[i][w].max(best[i - 1][w - weight] + value); // take it
}
}
}
best[n][capacity]
}
fn main() {
let items = [("tent", 6, 30), ("stove", 5, 20), ("camera", 5, 20)];
println!("best value: {}", knapsack(&items, 10));
}
best value: 40
That's O(n × capacity) time and memory. It's called pseudo-polynomial: it depends on the numeric value of the capacity, so a capacity of a billion grams needs a different approach (or coarser units).
One row is enough
Row i only reads row i - 1. So keep a single Vec of capacity + 1 entries and update it in place for each item, going through the capacities from high to low: then best[w - weight] still holds the value from before this item was considered, so each item is used at most once. Going from low to high would let an item be added again and again (that's the "unbounded" knapsack, where you can take as many copies as you like).
for &(weight, value) in items {
for w in (weight..=capacity).rev() {
best[w] = best[w].max(best[w - weight] + value);
}
}
Common mistakes
- Iterating capacities upward in the one-row version: items get reused.
- Forgetting the "skip" option, so every item that fits is forced in.
- Assuming the backpack must be full.
best[capacity]is the best value with at most that weight.
Your task
Write fn best_value(items: &[(usize, u32)], capacity: usize) -> u32 where each item is (weight, value), using a single Vec of capacity + 1 entries (no 2D table). The tests include 150 items and a capacity of 20,000.
Challenge 2
Two delivery vans must carry exactly the same total weight. Given the parcel weights, can they be split into two groups of equal total? Write fn can_split_evenly(weights: &[u32]) -> bool (no parcels: yes, two empty vans).
If the total is odd, it's impossible. Otherwise it's a knapsack question with booleans: can some subset reach exactly half the total? Keep can[s] for every sum s up to half, start with can[0] = true, and for each weight go through the sums from high to low: can[s] = can[s] || can[s - w]. The tests include over 100 parcels.
Challenge 3
Now the hiker wants to know which items to pack. Standard input has the capacity on the first line, then one item per line: name weight value. Print the chosen items in input order, the total weight and the total value:
take: stove, camera
weight: 10/10
value: 40
If nothing fits, the first line is take: nothing (the weight: and value: lines still follow, with 0s). The tests always have exactly one best choice.
Build the full 2D table from the lesson, then walk it backwards: starting at i = n and w = capacity, if best[i][w] differs from best[i - 1][w], item i - 1 was taken (subtract its weight from w). Reverse the list you collect to get input order.