While reading about 0/1 knapsack problem on the Internet, many tutorials considered value/weight ratio to solve the problem and I was wondering will it always contain the element with the greatest value/weight ratio to find an optimal solution to a 0/1 knapsack problem or is there any example where we find the optimal solution without the greatest ratio?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Knapsack is NP-complete. In particular, the greedy algorithm is not always optimal. This suggests that you should be able to find such an example. $\endgroup$– Yuval FilmusJun 12, 2021 at 17:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Consider this counterexample. Suppose the knapsack has a capacity 4. And suppose there are three items:
- Item A with weight 3 and value 5
- Item B with weight 2 and value 3
- Item C with weight 2 and value 3
The optimal solution contains items: B and C, in the knapsack with a total value = 6. However, item A has the highest value/weight ratio: 5/3, which is greater than 3/2.
answered Jun 12, 2021 at 18:08