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 w_{i }and is associated with a profit p_{i}. 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 x_{i} of object i is placed into the knapsack, then a profit p_{i}x_{i} 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

P_{i}X_{i}

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

P_{i}X_{I}

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 P_{i}/w_{I})

In the above problem it can be observed that, if the sum of all the weights is £
M then all x_{i} = 1, is an optimal solution. If we assume that the sum of all weights exceeds M, all x_{i}’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.