ITPEC FE Morning October 2023 Question 9
ITPEC FE Morning October 2023 — Question 9 of 80
0/1 Knapsack Problem — select items to maximize total price within a volume limit.
Given five items (A–E) with volumes and prices, knapsack capacity = 7:
- •A: vol=
3, price=4 - •B: vol=
2, price=3 - •C: vol=
3, price=5 - •D: vol=
1, price=2 - •E: vol=
5, price=9
Check each option:
- (a) A, B, D → vol: 3+2+1=6 ≤ 7 → price: 4+3+2=9
- (b) A, C, D → vol: 3+3+1=7 ≤ 7 → price: 4+5+2=11
- (c) B, E → vol: 2+5=7 ≤ 7 → price: 3+9=12 ✅
- (d) D, E → vol: 1+5=6 ≤ 7 → price: 2+9=11
Answer: (c) — B, E gives the highest total price of 12.
Greedy hint: Price-per-volume ratios: E=1.80, C=1.67, B=1.50, A=1.33, D=2.00. Take E first (vol=5), remaining capacity=2 → only B fits (vol=2). Total = 12.
Key rule: For 0/1 knapsack on the exam, check all given options — it's faster than solving optimally.
AI-generated — may contain errors
The original exam layout is preserved in the image so diagrams, formulas, tables, and code remain accurate.
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.