Knapsack problem algorithm, greedy algorithm

knapsack problem algorithm ,data design and analysis of algorithm ,greedy algorithm

1. Knapsack Problem  algorithm Department of Masters Of Computer Science(MCA) Central university of Karnataka Presented by: Prajjaval Rao Chintal 2018MCA09

2. What ? Given weights and values of n items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

3. Types   0-1 Knapsack problem In the 0-1 knapsack problem, we are not allowed to break items. We either take the whole item or don’t take it. Fractional Knapsack In fractional knapsack, we can break items for maximizing the total value of knapsack. This problem in which we can break an item is also called the fractional knapsack problem. THE OPTIMAL KNAPSACK ALGORITHM

4. example 0-1 KNAPSACK Take B and C Total weight =20+30=50 Total value =100+120=220 FRACTIONAL KNAPSACK Take A,B and 2/3 rd of C Total weight =10+20+(30* 2/3)=50 Total value =60+100+(120* 2/3)=240

5. Greedy approach The basic idea of the greedy approach is to calculate the ratio value/weight for each item. Sort the item on basis of this ratio. Then take the item with the highest ratio and add them until we can’t add the next item as a whole.  At the end add the next item as much (fraction) as we can.

6. Greedy approach solution Ratio= 6 Ratio= 5 Ratio= 4 calculate the ratio value/weight. Sort (descending) item on basis of ratio. Take item with highest ratio and add to knapsack until we cant add the next item as whole. At the end add the next item as much (fraction) as we can. Capacity left =40 Value = 60 Capacity left =20 Value = 160 Take 2/3 rd of C Weight = 2/3 *30 =20 Value = 2/3 *120 =80 Capacity left =0 Value = 240

7. THE OPTIMAL KNAPSACK ALGORITHM Input : an integer n Positive values wi and vi such that 1 <= i <= n Positive value W. Output : N values of xi such that 0 <= xi <=1 Total profit

8. Greedy knapsack algorithm Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) for i = 1 to n do x[ i ] = 0 // X is ratio of items weight = 0 //remaining weight of knapsack for i = 1 to n if weight + w[ i ] ≤ W //W is total capacity of bag then x[ i ] = 1 weight = weight + w[ i ] //w[ i ] is the weight of item else x[ i ] = (W - weight) / w[ i ] weight = W break return x Time complexity If the provided items are already sorted into a decreasing order of then the whileloop takes a time in  O(n ). As main time taking step is sorting, the whole problem can be solved in O(n log n) only. I t can be O(n^2),O(n^3) anything greater than O( nlogn ). BUT we usually consider the tightest upper bound that is O( nlogn ).

9. Thank you