Packing the best bag by table

Computing · Algorithms & Data Structures · ages 20-22

Name ______________________ Date ____________

What question does each cell answer?
- Buy or sell the shop
- Paint the bag red
- Take this item or skip it
What is the knapsack table indexed by?
- Item and remaining capacity
- Color and brand
- Price and shop name
Why is the method called pseudo-polynomial?
- It never finishes
- It uses no tables
- Its cost follows the numbers in the input
Same items, capacity 5. Which items does the traceback take?
- The third item alone
- The first two items
- All three items
Weights 2, 3, 4 with values 3, 4, 5 and capacity 5. Give the best value.
Answer: ______________
The same item can be worth taking at one capacity and wrong at another.
Circle one: True False
Reading the corner value alone tells you which items were taken.
Circle one: True False
All weights double but items stay three. A friend says the work stays the same. What is wrong?
- Nothing, counts decide alone
- Doubled weights double the columns and the work
- Tables shrink when numbers grow

Answer key

For grown-ups. Fold this page away before handing over the rest.

Take this item or skip it · Each cell compares taking against skipping at that capacity.
Item and remaining capacity · Rows add items, columns track room left.
Its cost follows the numbers in the input · Bigger weights mean more columns, even with the same item count.
The first two items · Weight 5 exactly, value 7, which the corner confirms.
7 · Items one and two weigh 5 and value 7, beating any other fit.
True · Room left changes the trade, which is why capacity is an axis.
False · The corner gives the value; only the traceback names the items.
Doubled weights double the columns and the work · Table size follows the numbers, so larger weights cost more.