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)
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.
