4
$\begingroup$

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?

$\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$ Jun 12, 2021 at 17:49

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.