Knapsack Problem

Today we will try to apply the greedy method to solve one of the simply complex problem Knapsack Problem.

• Given n objects and a Knapsack where object i has a weight w_i and the Knapsack has a capasity m
• If a fraction x_i of object i placed into knapsack, a profit p_ix_i is earned
• The objective is to obtain a filling of Knapsack maximizing the total profit

Problem Formulation:

First Know the Greedy method control abstraction for the subset paradigm

---

AlgorithmGreedy(a,n)
{
solution:=null;
For i: 1 to n do
{
x = Select(a);
if feasible(solution,x) then
solution = Union(solution,x)
}
return solution;
}

---

Let's consider a knapsack problem of finding the optimal solution here, M = 15, (p1,p2,p3,...p7) = (10,5,15,7,6,18,3) and (w1, w2,..w7) = (2,3,5,7,1,4,1).

Now we will find the solution by following "maximum profit per unit of capacity" Strategy:

Let (a,b,c,d,e,f,g) represent the items with profit (10,5,15,7,6,18,3).

This means that the objects are considered in deceasing order of the ratio P₁/w₁.

a: P₁/w₁ = 10/2 = 5;

b: P₂/w₂ = 5/3 = 1.66;

c: P₃/w₃ = 15/5 = 3

d: P₄/w₄ = 7/7 =1

e: P₅/w₅ = 6/1 = 6

f: P₆/w₆ = 18/4 = 4.5

g: P₇/w₇ = 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	2-2 =0	2/3*5=3.33

Profit = 55.33 units. The solution set is(1,2/3,10,1,1,1).