The knapsack problem
The 0/1 knapsack and its fractional version: the greedy rule by value-to-weight ratio and its limits, dynamic programming on the capacity, the fractional bound and branch and bound.
- 23 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
A few cards from the deck
Knapsack problem: what is it?
Show the answer
Choose among items, each with a given weight and value, the ones to take so as to maximise the total value without exceeding the capacity.
In the 0/1 version, each item is taken whole or left; in the fractional version, a share of an item may be taken.
Capacity 50; items (weight, value): A (10, 60), B (20, 100), C (30, 120). What does the greedy rule by value-to-weight ratio return, and what is the 0/1 optimum?
- Greedy: 160 (A and B); optimum: 220 (B and C)
- Greedy: 220 (B and C); optimum: 220 (B and C), greedy gets there here
- Greedy: 160 (A and B); optimum: 160, no other combination does better
- Greedy: 160 (A and B); optimum: 180 (A and C)
Show the answer
Greedy: 160 (A and B); optimum: 220 (B and C)
Ratios: A 6, B 5, C 4. The greedy rule takes A and B (weight 30, value 160); C weighs 30 and no longer fits (20 left). But B + C weighs exactly 50, which is allowed, for 220: better than A + C (180).
For the 0/1 knapsack with n items and capacity W, the dynamic programming table has one row per … and one column per … from 0 to W, hence a running time of O(nW).
Show the answer
For the 0/1 knapsack with n items and capacity W, the dynamic programming table has one row per item and one column per capacity from 0 to W, hence a running time of O(nW).
One cell for each pair (number of items considered, capacity), plus a row 0 with no item and a column for capacity 0. Each cell is computed in constant time from the previous row.
Greedy algorithm: what is it?
Show the answer
A method that builds a solution through a series of choices, each made as well as possible at the moment and never reconsidered.
For the knapsack: sort by decreasing value-to-weight ratio, then take items while they fit. Optimal for the fractional version, not for 0/1.