Ask a Question

sanchayita

The Fractional Knapsack Method In the knapsack problem we have a knapsack of a fixed capacity (say W pounds) and different items i each with a given weight wi and a given benefit bi. We want to put items into the knapsack so as to maximize the benefit subject to the constraint that the sum of the weights must be less than W. The knapsack problem is actually rather difficult in the normal case where one must either put an item in the knapsack or not. However, in this section, in order to illustrate greedy algorithms, we consider a much simpler variation in which we can take part of an item and get a proportional part of the benefit. This is called the ``fractional knapsack problem'' since we can take a fraction of an item. (The more common knapsack problem is called the ``0-1 knapsack problem'' since we either take all (1) or none (0) of an item. In symbols, for each item i we choose an amount xi (0≤xi≤wi) that we will place in the knapsack. We are subject to the constraint that the sum of the xi is no more than W since that is all the knapsack can hold. We again desire to maximize the total benefit. Since, for item i, we only put xi in the knapsack, we don't get the full benefit. Specifically we get benefit (xi/wi)bi. But now this is easy! Item i has benefit bi and weighs wi. So its value (per pound) is vi=bi/wi. We make the greedy choice and pick the most valuable item and take all of it or as much as the knapsack can hold. Then we move to the second most valuable and do the same. This clearly is optimal since it never makes sense to leave over some valuable item to take some less valuable item. Why doesn't this work for the normal knapsack problem when we must take all of an item or none of it? Example: W=6, w1=4, w2=w3=3, b1=5, b2=b3=3. So v1=5/4, v2=v3=1 Start with the most valuable item, number 1 and put it n the knapsack. Knapsack can hold 7-4=2 more "pounds" but remaining items won't fit So the total benefit carried is 5. The right solution is to take items 2 and 3 for a total benefit of 6. The difference between this item and fractional knapsack is that the knapsack can still hold 2/3 of item 2, but we can't take part of an item as we can in the fractional knapsack problem. Algorithm algorithm FractionalKnapsack(S,W): Input: Set S of items i with weight wi and benefit bi all positive. Knapsack capacity W>0. Output: Amount xi of i that maximizes the total benefit without exceeding the capacity. for each i in S do xi ← 0 { for items not chosen in next phase } vi ← bi/wi { the value of item i "per pound" } w ← W { remaining capacity in knapsack } while w > 0 do remove from S an item of maximal value { greedy choice } xi ← min(wi,w) { can't carry more than w more } w ← w-xi Analysis FractionalKnapsack has time complexity O(NlogN) where N is the number of items in S.