5.2 General Knapsack problem:
Greedy
method is best suited to solve more complex problems such as a knapsack
problem. In a knapsack problem there is a knapsack or a container of
capacity M n items where, each item i is of weight wi and is associated with a profit pi.
The problem of knapsack is to fill the available items into the
knapsack so that the knapsack gets filled up and yields a maximum
profit. If a fraction xi of object i is placed into the knapsack, then a profit pixi is earned. The constrain is that all chosen objects should sum up to M
Illustration
Consider a knapsack problem of finding the optimal solution where,
M=15, (p1,p2,p3…p7) = (10, 5, 15, 7, 6, 18, 3) and (w1, w2, …., w7) =
(2, 3, 5, 7, 1, 4, 1).
In order to find the solution, one can follow three different srategies.
Strategy 1 : non-increasing profit values
Let (a,b,c,d,e,f,g) represent the items with profit
(10,5,15,7,6,18,3) then the sequence of objects with non-increasing
profit is (f,c,a,d,e,b,g).
|
Item chosen for inclusion |
Quantity of item included |
Remaining space in M |
PiXi |
|
f |
1 full unit |
15-4=11 |
18*1=18 |
|
C |
1 full unit |
11-5=6 |
15*1=15 |
|
A |
1 full unit |
6-2=4 |
10*1=10 |
|
d |
4/7 unit |
4-4=0 |
4/7*7=04 |
Profit= 47 units
The solution set is (1,0,1,4/7,0,1,0).
Strategy 2: non-decreasing weights
The sequence of objects with non-decreasing weights is (e,g,a,b,f,c,d).
|
Item chosen for inclusion |
Quantity of item included |
Remaining space in M |
PiXI |
|
E |
1 full unit |
15-1=14 |
6*1=6 |
|
G |
1 full unit |
14-1=13 |
3*1=3 |
|
A |
1 full unit |
13-2=11 |
10*1=10 |
|
b |
1 full unit |
11-3=8 |
5*1=05 |
|
f |
1 full unit |
8-4=4 |
18*1=18 |
|
c |
4/5 unit |
4-4=0 |
4/5*15=12 |
Profit= 54 units
The solution set is (1,1,4/5,0,1,1,1).
Strategy 2: maximum profit per unit of capacity used
(This means that the objects are considered in decreasing order of the ratio Pi/wI)
a: P1/w1 =10/2 = 5 b: P2/w2 =5/3=1.66 c: P3/w3 =15/5 = 3
d: P4/w4 =7/7=1 e: P5/w5 =6/1=6 f: P6/w6 =18/4 = 4.5
g: P7/w7 =3/1=3
Hence, the sequence is (e,a,f,c,g,b,d)
|
Item chosen for inclusion |
Quantity of item included |
Remaining space in M |
PiXI |
|
E |
1 full unit |
15-1=14 |
6*1=6 |
|
A |
1 full unit |
14-2=12 |
10*1=10 |
|
F |
1 full unit |
12-4=8 |
18*1=18 |
|
C |
1 full unit |
8-5=3 |
15*1=15 |
|
g |
1 full unit |
3-1=2 |
3*1=3 |
|
b |
2/3 unit |
2-2=0 |
2/3*5=3.33 |
Profit= 55.33 units
The solution set is (1,2/3,1,0,1,1,1).
In the above problem it can be observed that, if the sum of all the weights is £
M then all xi = 1, is an optimal solution. If we assume that the sum of all weights exceeds M, all xi’s
cannot be one. Sometimes it becomes necessary to take a fraction of
some items to completely fill the knapsack. This type of knapsack
problems is a general knapsack problem.
click here for more details:
http://www.vyomworld.com/gate/cs/ada/5.2.asp - http://www.vyomworld.com/gate/cs/ada/5.2.asp
|