Knapsack problem using greedy approach

In shared PPT we have discussed Knapsack problem using greedy approach and its two types i.e Fractional and 0-1

1. Dept. of IT & MCA knapsack problem using greedy approach Group no: 13 Padmesh agrekar : 04 Revati jalnekar : 24 Akshay kamble : 28 Sonal kumar : 52 Ameyaa vaidya : 57 Guided by: Prof. Neelam Chandolikar

2. Content Introduction to greedy algorithm Knapsack problem Example of fractional knapsack Example of 0/1 knapsack Algorithm and complexity of fractional knapsack Algorithm and complexity of 0/1knapsack Application of knapsack

3. Introduction A  greedy algorithm  is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem. Greedy algorithms are quite successful in some problems, such as  Huffman encoding   which is used to compress data, or   Dijkstra's algorithm , which is used to find the shortest path through a graph. Steps for achieving a Greedy Algorithm are: Feasible Local optimal unalterable

4. A greedy algorithm works if a problem exhibits the following two properties: Greedy Choice Property Optimal substructure Applications of Greedy Greedy approach is used to solve many problems, such as Finding the shortest path between two vertices using Dijkstra’s algorithm. Finding the minimal spanning tree in a graph using Prim’s /Kruskal’s algorithm, etc.

5. Knapsack problem Definition: Knapsack problem states that: Given a set of items, each with a weight and a profit, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total profit is as large as possible

6. Versions of knapsack There are two versions of knapsack problem: 1. 0/1 Knapsack Problem: Items are indivisible; you either take them or not. And it is solved using Dynamic Programming(DP). 2. Fractional Knapsack Problem: Items are divisible; you can take any fraction of an item. And it is solved using Greedy Algorithm.

7. Example of fractional knapsack   Consider n=5 and m=100 V(p) 20 30 66 40 60 W 10 20 30 40 50 v/w 2.0 1.5 2.2 1.0 1.2 After sorting 2 3 1 5 4 T ake the items in sorted manner: w=30+10+20+40 out of 50 value=66+20+30+.8*60=164

8. Example of 0/1 knapsack 0-1knapsack Consider n=5 and m=15 T ake the items in sorted manner w=7+6+2=15 value=28+22+discard+discard+2=52 V(p) 18 8 2 22 28 w 5 4 2 6 7 v/w 3.60 2 1 3.66 4 After sorting 3 4 5 2 1

9. Algorithm of fractional knapsack for i =1 to n { compute pi/wi; } sort objects in non- increasing order p/w; for i =1 to n { if(m>0 && wi<=m) m = m - wi; P = P + pi; else break; } if(m>0) { P=P+ pi*(m/wi); }

10. complexity The complexity of the algorithm: If using a simple sort algorithm (selection, bubble…) then the complexity of the whole problem is O(n2). If using quick sort or merge sort then the complexity of the whole problem is O( nlogn ).

11. Algorithm and complexity of 0/1 knapsack   Knapsack_DP(n,W) 1. for w = 1 to m 2. do B[0,w] 0 3. for i = 1 to n 4. do B[i,0] 0 5. for w = 1 to m 6. do if (Wi < = w && B[i-1,w-Wi] +bk > B[i-1,w] 7. then B[i,w] B[i-1,w-Wi]+bk 8. else B[i,w] B[i-1,w]  Complexity:  Clearly the dynamic programming algorithm for the knapsack problem has a time complexity of O( n.w ) . Where , n= the number of items & w= the capacity of the knapsack.

12. Application of knapsack Knapsack problems appear in real world decision making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials , selection of investment and selection of assets. In many cases of resource allocation along with some constraint, the problem can be derived in a similar way of Knapsack problem. Following is a set of example. Finding the least wasteful way to cut raw materials portfolio optimization Cutting stock problems

13. References: https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_greedy_method.htm#:~:text=Greedy%20algorithms%20build%20a%20solution,it%20gives%20an%20immediate%20benefit.&text=Hence%2C%20we%20can%20say%20that,of%20finding%20global%20optimal%20solution. https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/tutorial/