Skip to content
Get started

When the best ratio is not the best pack

A knapsack holds weight at most 1515. Each item can be taken at most once:

itemABCDEF
weight745362
value42222615278

What is the maximum total value?

Show hints (2)+
  1. Try the best-ratio greedy first and notice how much capacity it wastes.
  2. Use the DP V[c]=max⁡(V[c],V[c−w]+v)V[c] = \max(V[c], V[c-w]+v) with capacity iterated downward.

Answer

Reveal answer →

83

Create a free account to see the full worked solution and track your progress.

Interview format: Trading Aptitude Tests, Prop Trading

Related questions