Question

For given capacity of knapsack W and n items {i1,i2,...,in} with its own value {v1,v2,...,vn} and weight {w1,w2,...,wn}, find a greedy algorithm that solves fractional knapsack problem, and prove its correctness.

And, if you naively use the greedy algorithm to solve 0-1 knapsack problem with no repetition, then the greedy algorithm does not ensure an optimal solution anymore. Give an example that a solution from the greedy algorithm is not an optimal solution for 0-1 knapsack problem.

Answer 1

For example if we have Sack size=7 items with weight wt value 1 valueſ weight 9บ 1 1 1.33 3 4 5 I init 1.25 1.4 If we apply greedy left space we solution for this problem then we will consider first the item with higher value/weight ration then we will get item d and a with maximum value of sack to be 8. Because this is not fractional knapsack and a weighs total of 6 in sack item b and c But we can clearly see if we choose and maximum sack as item a we get total weight of 7 value = = 9. Thus greedy algorith is not always an optional solution 0-1 knapsack problem. in case of

NOTE: I TRIED TO IMPLEMENT THE REQUESTED PROBLEM AS PER BEST OF MY UNDERSTANDING....IF YOU NEED ANY SORT OF HELP REGARDING THIS PROBLEM , PLEASE DO MENTION IN COMMENTS.....IF YOU GOT ANY SORT OF HELP THROUGH THIS ARTICLE PLEASE DO UPVOTE.....THANKYOU!!!