Knapsack problem using Greedy method.pptx

This presentation describes about Greedy approach and knapsack problem. It also illustrates one example for knapsack problem.

1. Greedy Algorithm – Knapsack Problem Mrs.S.RAJAPRIYA , M.S(IT)., Assistant Professor, Department of Computer Science (self) V.V.Vanniaperumal College for Women, Virudhunagar

2. Greedy Method The greedy method is a simple strategy of progressively building up a solution, one element at a time, by choosing the best possible element at each stage. At each stage, a decision is made regarding whether or not a particular input is in an optimal solution. This is done by considering the inputs in an order determined by some selection procedure. If the inclusion of the next input, into the partially constructed optimal solution will result in an infeasible solution then this input is not added to the partial solution.

3. Greedy Method The selection procedure itself is based on some optimization measure. This version of greedy technique is called subset paradigm .

4. 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 knapsack so that total weight is less than or equal to the maximum limit and the total profit is as large as possible.

5. Versions of Knapsack

6. Fractional Knapsack using Greedy Method The basic idea of the greedy approach is to calculate the ratio profit/weight for each item. Sort the item on the basis of this ratio. Then take the item with the highest ratio and add them as much as we can (can be the whole element or a fraction of it). This will always give the maximum profit because, in each step it adds an element such that this is the maximum possible profit for that much weight.

7. Example Consider the example: Given the weights and profits of N items, in the form of {profit, weight} put these items in a knapsack of capacity W to get the maximum total profit in the knapsack. items = {{100, 20}, {60, 10}, {120, 30}}, W = 50. Profit/Weight ratio calculation: 100/20 = 5 60/10 = 6 120/30 = 4 Sorting: Initially sort the array based on the profit/weight ratio. The sorted array will be {{60, 10}, {100, 20}, {120, 30}}.

8. Example Iteration: For i = 0, weight = 10 which is less than W. So add this element in the knapsack. profit = 60 and remaining W = 50 – 10 = 40 . For i = 1, weight = 20 which is less than W. So add this element too. profit = 60 + 100 = 160 and remaining W = 40 – 20 = 20 . For i = 2, weight = 30 is greater than W. So add 20/30 fraction = 2/3 fraction of the element. Therefore profit = 2/3 * 120 = 80 = 80 + 160 = 240 and remaining W becomes 0. So the final profit becomes 240 for W = 50.

9. Algorithm

10. Running time The objects are to be sorted into descending order of pi / wi ratio. But if we disregard the time to initially sort the objects, the algorithm requires only O(n) time

11. Thank You