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?
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.