When the best ratio is not the best pack
A knapsack holds weight at most . Each item can be taken at most once:
| item | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| weight | 7 | 4 | 5 | 3 | 6 | 2 |
| value | 42 | 22 | 26 | 15 | 27 | 8 |
What is the maximum total value?
Show hints (2)+
- Try the best-ratio greedy first and notice how much capacity it wastes.
- Use the DP with capacity iterated downward.
Answer
Reveal answer →Final answer
83
Create a free account to see the full worked solution and track your progress.
Interview format: Trading Aptitude Tests, Prop Trading