ITPEC FE Morning October 2023 Question 9
In the table below, there are five items A through E. Each item cannot be divided into smaller pieces. When a knapsack with a maximum volume of 7 units is used for carrying the items, which of the following is a set of items to be packed in the knapsack so that the total price can be maximized?
Explanation
B and E, total price 12 — the best set of whole items that fits in volume 7.
All four fit, and B, E has the highest price. It is also the true optimum: with E (volume 5) the remaining 2 units hold at most B, worth 3; without E, the best fit is A, C, D at 11.
Answer (c)
Why not others:
- •(a) A, B, D — price 9, and it leaves one unit of volume unused
- •(b) A, C, D — fills the knapsack but is worth only 11, because A has the lowest price per unit of volume
- •(d) D, E — the greedy choice by price per volume (D 2.0, E 1.8): after D and E only one unit is left and nothing else fits, so it stops at 11
Key rule: In the 0/1 knapsack problem items cannot be split, so greedy selection by price-per-volume can miss the optimum; compare the complete feasible sets.
Algorithm and Programming · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.