به انگلیسی

Packing the best bag by table

Computing · Algorithms & Data Structures · ages 20-22

Name ______________________ Date ____________

If item i fits at capacity c, what does K(i,c) compare?
- Taking it repeatedly until the bag is full
- Taking it whenever its weight is smallest
- Skipping it or taking it once
What do the indices of K(i,c) represent in the taught 0/1 knapsack table?
- An item prefix and allowed capacity
- An item value and selected-item count
- A total profit and remaining-item count
Why is O(n(W+1)) knapsack table work called pseudo-polynomial for binary-encoded inputs?
- It is polynomial in every input's bit length
- It depends only on how many items are listed
- It is polynomial in numeric capacity W
Weights are 2, 3, 4; values are 3, 4, 6; capacity is 6. The table gives K(3,6)=9, K(2,6)=7, K(2,2)=3 and K(1,2)=3. Which items does traceback select?
- Items 1 and 2, leaving item 3
- Items 1 and 3, leaving item 2
- Items 2 and 3, leaving item 1
A 0/1 knapsack has weights 1, 3, 4 and corresponding values 2, 5, 6. Capacity is 4. Give the maximum value.
Answer: ______________
Two items each weigh 2 and have values 3 and 5. Capacity is 2. The value-3 item fits but is excluded from every optimal selection.
Circle one: True False
The single value K(n,W), without traceback or other information, identifies which items were selected.
Circle one: True False
All weights and the capacity W are doubled, with the same items and values. For the uncompressed capacity table, what changes?
- Both item rows and capacity columns double
- Columns change from W+1 to 2W+1
- Columns stay fixed because item count is fixed

Answer key

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

Skipping it or taking it once · The cell compares the previous-row skip value with the item's value plus the previous-row value at reduced capacity.
An item prefix and allowed capacity · i limits choices to the first i items. c limits their total weight to at most c.
It is polynomial in numeric capacity W · Numeric W can be exponentially large in the number of bits that encode it. A polynomial bound in W is not a polynomial bound in input length.
Items 1 and 3, leaving item 2 · 9 differs from 7, so take item 3 and reduce capacity to 2. Equal values in rows 2 and 1 allow skipping item 2. Item 1 supplies the remaining value 3.
7 · The first two items weigh 4 and give value 7. The third alone gives 6; all other fitting sets give less than 7.
True · Only one item fits at a time. Taking the value-5 item beats taking the value-3 item or taking neither.
False · K(n,W) gives an optimal value. Traceback recovers a selection, and tied choices may allow different selections with that value.
Columns change from W+1 to 2W+1 · Capacity columns include zero through the allowed capacity. Doubling W gives 2W+1 columns; the item rows do not change.