Given a set of items, each with a weight (wi) and a value (vi), 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 value is as large as possible.
Alternatively,
US Pizza gives you a bowl that can hold 100 gms of salad. You have different salad items each having its own Nutritional Value (NV) and availability. You are supposed to find the way one should fill his bowl so that he gets maximum nutrition. They need not take all of the available quantity. Taking a fraction of the salad item is allowed.
Items Nutrition Value per Gram Available
Noodle 10 100 gm
Soyabean 30 15 gm
Macroni 5 100 gm
Fruits 40 10 gm
Strategy:
It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.
Define m[i,w] to be the maximum value that can be attained with weight less than or equal to w using items up to i.
We can define m[i,w] recursively as follows:
• m[0,w] = 0
• m[i,0]=0
• m[i,w] = m[i-1,w] if wi > w (the new item is more than the current weight limit so this element cannot be accepted because it’s weight is larger than w )
• m[i,w] = max(m[i-1,w] ,m[i-1,w-wi ] + vi) if wi < = w.
The solution can then be found by calculating m[n,W]. To do this efficiently we can use a table to store previous computations. This solution will therefore run in O(nW) time and O(nW)space.
Solution to alternate problem:
All we need to do here is start with the item that provides the highest nutrition/gram and take the maximum available quantity unless the bowl is full. If after this, the bowl still has space, you take the item with the second highest nutrition/gram value. And so on.
I am sure you get the idea. For the given example, you would take 10 gm of Fruits (Full = 10, Remaining = 90), 15 gm of Soyabean (Full = 25, Remaining = 75), and to fill up the rest, with 75 gm of Noodles (Full = 100, Remaining = 0). In this way of selection, you get the maximum nutritional value, 1600 (10*40 + 15*30 + 75*10).
Alternatively,
US Pizza gives you a bowl that can hold 100 gms of salad. You have different salad items each having its own Nutritional Value (NV) and availability. You are supposed to find the way one should fill his bowl so that he gets maximum nutrition. They need not take all of the available quantity. Taking a fraction of the salad item is allowed.
Items Nutrition Value per Gram Available
Noodle 10 100 gm
Soyabean 30 15 gm
Macroni 5 100 gm
Fruits 40 10 gm
Strategy:
It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.
Define m[i,w] to be the maximum value that can be attained with weight less than or equal to w using items up to i.
We can define m[i,w] recursively as follows:
• m[0,w] = 0
• m[i,0]=0
• m[i,w] = m[i-1,w] if wi > w (the new item is more than the current weight limit so this element cannot be accepted because it’s weight is larger than w )
• m[i,w] = max(m[i-1,w] ,m[i-1,w-wi ] + vi) if wi < = w.
The solution can then be found by calculating m[n,W]. To do this efficiently we can use a table to store previous computations. This solution will therefore run in O(nW) time and O(nW)space.
Solution to alternate problem:
All we need to do here is start with the item that provides the highest nutrition/gram and take the maximum available quantity unless the bowl is full. If after this, the bowl still has space, you take the item with the second highest nutrition/gram value. And so on.
I am sure you get the idea. For the given example, you would take 10 gm of Fruits (Full = 10, Remaining = 90), 15 gm of Soyabean (Full = 25, Remaining = 75), and to fill up the rest, with 75 gm of Noodles (Full = 100, Remaining = 0). In this way of selection, you get the maximum nutritional value, 1600 (10*40 + 15*30 + 75*10).
No comments:
Post a Comment