23CS2205A
DESIGN AND ANALYSIS OF
ALGORITHMS
1
KNAPSACK PROBLEM
You are given the following-
• A knapsack (kind of shoulder bag) with limited weight capacity.
• Few items each having some weight and value.
The problem states-
Which items should be placed into the
knapsack such that-
• The value or profit obtained by
putting the items into the knapsack is
maximum.
• And the weight limit of the
knapsack does not exceed.
2
KNAPSACK PROBLEM VARIANTS &
ITS DIFFERENCES
Variants:
• 0/1 Knapsack. • Fractional Knapsack
• can break items for maximizing the
• not allowed to break items. We total value of knapsack
either take the whole item or don’t
take it.
10kg 4kg 8kg
$10 $5 $20
7kg 2kg 6kg
$10 $3 $11
4kg 8kg
$2 $17
3
0/1 KNAPSACK PROBLEM
In 0/1 Knapsack Problem,
• As the name suggests, items are indivisible here.
• We can not take the fraction of any item.
• We have to either take an item completely or leave it completely.
Example:
Consider the knapsack instance n = 3, (w1, w2, w3) = (2, 3, 4), (p1, p2, p3) = (1, 2, 5)
and m = 6.
Probability of Chosen Items (xi) = [{0, 0, 0}, {0, 0, 1}, ……, {1, 1, 1}]
No. of Possible Solutions (2n) = 23 = 8.
The problem is to find the Best Optimal Solution among the 8 for the 0/1 Knapsack.
4
0/1 KNAPSACK PROBLEM
1. Let fi(yj) be the values of optimal solution. Then S i is a pair (p,w)
where p = f (yj) and w = yj
Initially S0 = { (0,0) }. We can compute Si+1 from Si. The
Computations of Si are sequence of decisions made for obtaining
optimal solution.
2. Let xn be the optimal sequence. Then there are two instances {x n} and
{xn-1,…..,x1 }. So from {xn-1,…..,x1} will choose optimal sequence
with respect to xn.
5
0/1 KNAPSACK PROBLEM
3. The formulas that are used while solving 0/1 knapsack
problem.
Let fn(m) be the value of an optimal solution, then
fn(m)= max { fn-1(m), fn-1( m - wn) + pn }
General formula
fi(y)= max { fi-1(y), fi-1( y - wi) + pi }
6
0/1 Knapsack Problem – Solution
Consider the knapsack instance n = 3, (w1, w2, w3) = (2, 3, 4), (p1, p2, p3) = (1, 2, 5) and m = 6.
fn(m)= max { fn-1(m), fn-1( m - wn) + pn }
f3(6)= max { f2(6), f2( 6 – w3) + p3 }
f3(6)= max { f2(6), f2( 6 – 4) + 5 }
f3(6)= max { f2(6), f2( 2) + 5 }
0/1 Knapsack Problem – Solution
Consider the knapsack instance n = 3, m=6
(w1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
f3(6)= max { f2(6), f2( 2) + 5 }
f2(6)= max { f1(6), f1( 6-3) + 2 } f2(2)= max { f1(2), f1( 2-3) + 2 }
f2(6)= max { f1(6), f1( 3) + 2 } f2(2)= max { f1(2), f1( -1) + 2 }
0/1 Knapsack Problem – Solution
Consider the knapsack instance n = 3, m=6
(w1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
f3(6)= max { f2(6), f2( 2) + 5 }
f2(6)= max { f1(6), f1( 3) + 2 } f2(2)= max { f1(2), f1( -1) + 2 }
f1(6)= max { f0(6), f0( 6-2) + 1 } f1(3)= max { f0(3), f0( 3-2) + 1 }
f1(6)= max { f0(6), f0( 4) + 1 } f1(3)= max { f0(3), f0( 1) + 1 }
f1(6)= max { 0, 0 + 1 } = 1 f1(3)= max { 0, 0 + 1 } = 1
0/1 Knapsack Problem – Solution
Consider the knapsack instance n = 3, m=6
(w1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
f3(6)= max { f2(6), f2( 2) + 5 }
f2(6)= max { 1, 1 + 2 } f2(2)= max { f1(2), f1( -1) + 2 }
f1(6)= max { f0(6), f0( 6-2) + 1 } f1(3)= max { f0(3), f0( 3-2) + 1 }
f1(6)= max { f0(6), f0( 4) + 1 } f1(3)= max { f0(3), f0( 1) + 1 }
f1(6)= max { 0, 0 + 1 } = 1 f1(3)= max { 0, 0 + 1 } = 1
0/1 Knapsack Problem – Solution
Consider the knapsack instance n = 3, m=6
(w1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
f3(6)= max { f2(6), f2( 2) + 5 }
f2(6)= max { 1, 3 } = 3 f2(2)= max { f1(2), f1( -1) + 2 }
0/1 Knapsack Problem – Solution
Consider the knapsack instance n = 3, m=6
(w1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
f3(6)= max { f2(6), f2( 2) + 5 }
f2(6)= max { 1, 1 + 2 } f2(2)= max { f1(2), f1( -1) + 2 }
f1(2)= max { f0(2), f0( 2-2) + 1 } f1( -1)
f1(2)= max { 0, 0 + 1 } = 1 -INF
0/1 Knapsack Problem – Solution
Consider the knapsack instance n = 3, m=6
(w1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
f3(6)= max { f2(6), f2( 2) + 5 }
f2(6)= max { 1, 1 + 2 } f2(2)= max { 1, -INF + 2 }
f1(2)= max { f0(2), f0( 2-2) + 1 } f1( -1)
f1(2)= max { 0, 0 + 1 } = 1 -INF
0/1 Knapsack Problem – Solution
Consider the knapsack instance n = 3, m=6
(w1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
f3(6)= max { f2(6), f2( 2) + 5 }
f2(6)= max { 1, 1 + 2 } f2(2)= max { 1, -INF + 2 }
0/1 Knapsack Problem – Solution
Consider the knapsack instance n = 3, m=6
(w1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
f3(6)= max { f2(6), f2( 2) + 5 }
f2(6)= max { 1, 3 } = 3 f2(2)= max { 1, -INF} = 1
0/1 Knapsack Problem – Solution
Consider the knapsack instance n = 3, m=6
(w1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
f3(6)= max { 3, 1 + 5 }
f2(6)= max { 1, 3 } = 3 f2(2)= max { 1, -INF} = 1
0/1 Knapsack Problem – Solution
Consider the knapsack instance n = 3, m=6
(w1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
f3(6)= max { 3, 1 + 5 } = 6
0/1 Knapsack Problem – Solution: Set
Method
Initially S0 = {(0,0)}
S1i ={ ( P,W) / (P- pi+1,W- wi+1) ϵ Si }
Si+1 can be computed by merging from Si and S1i
Purging or dominance rule: if Si+1 contains two pairs (pj, wj ) and (pk, wk ) with
the property that pj ≤ pk and wj ≥ wk then the pair (pj, wj ) can be discarded.
When generating Si, we can also purge all pairs ( p, w ) with w > m as these pairs
determine the value of f n (x) only for x > m.
The optimal solution f n (m) is given by the highest profit pair.
0/1 Knapsack Problem – Solution: Set
Method
Consider the knapsack instance n = 3, m=6 (w 1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
Initially S0 = {(0,0)}
S1i ={ ( P,W) / (P- pi+1,W- wi+1) ϵ Si }
Si+1 can be computed by merging from Si and S1i
0/1 Knapsack Problem – Solution: Set
Method
Consider the knapsack instance n = 3, m=6 (w 1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
S0 = {(0,0)} S10 ={ ( 1, 2) }
S1 = {(0, 0), (1, 2)} S11 ={ (2, 3), ( 3, 5) }
S2 = {(0, 0), (1, 2), (2, 3), ( 3, 5) } S12 ={ (5, 4), ( 6, 6), (7, 7), (8, 9) }
S3 = {(0, 0), (1, 2), (2, 3), ( 3, 5), (5, 4), ( 6, 6), (7, 7), (8, 9) }
S1i ={ ( P,W) / (P- pi+1,W- wi+1) ϵ Si }
0/1 Knapsack Problem – Solution: Set
Method
Consider the knapsack instance n = 3, m=6 (w 1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
S0 = {(0,0)} S10 ={ ( 1, 2) }
S1 = {(0, 0), (1, 2)} S11 ={ (2, 3), ( 3, 5) }
S2 = {(0, 0), (1, 2), (2, 3), ( 3, 5) } S12 ={ (5, 4), ( 6, 6), (7, 7), (8, 9) }
S3 = {(0, 0), (1, 2), (2, 3), ( 3, 5), (5, 4), ( 6, 6)}
S1i ={ ( P,W) / (P- pi+1,W- wi+1) ϵ Si }
Si+1 can be computed by merging from Si and S1i
0/1 Knapsack Problem – Solution: Set
Method
Consider the knapsack instance n = 3, m=6 (w 1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
S0 = {(0,0)} S10 ={ ( 1, 2) }
S1 = {(0, 0), (1, 2)} S11 ={ (2, 3), ( 3, 5) }
S2 = {(0, 0), (1, 2), (2, 3), ( 3, 5) } S12 ={ (5, 4), ( 6, 6), (7, 7), (8, 9) }
S3 = {(0, 0), (1, 2), (2, 3), (5, 4), ( 6, 6)}
S1i ={ ( P,W) / (P- pi+1,W- wi+1) ϵ Si }
Si+1 can be computed by merging from Si and S1i
0/1 Knapsack Problem – Solution: Set
Method
Consider the knapsack instance n = 3, m=6 (w 1, w2, w3) = (2, 3, 4) & (p1, p2, p3) = (1, 2, 5).
S0 = {(0,0)} S10 ={ ( 1, 2) }
S1 = {(0, 0), (1, 2)} S11 ={ (2, 3), ( 3, 5) }
S2 = {(0, 0), (1, 2), (2, 3), ( 3, 5) } S12 ={ (5, 4), ( 6, 6), (7, 7), (8, 9) }
S3 = {(0, 0), (1, 2), (2, 3), (5, 4), ( 6, 6)}
S1i ={ ( P,W) / (P- pi+1,W- wi+1) ϵ Si }
Si+1 can be computed by merging from Si and S1i
Example 1: Consider the knapsack instance n = 3,
(w1,w2,w3) = (2,3,4), (p1,p2,p3) = (1,2,5), and m = 6.
Initially
S0 = {(0,0)}
Include 1st object
S10 ={ ( 0+1,0+2) }= { (1,2) }
Next Stage can be obtained S0+1 (S1 )can be computed by merging from S0 and S10
S1 ={(0,0)(1,2)}
Include 2nd object
S11 ={ ( 0+2,0+3) (1+2, 2+3) }= { (2,3) (3,5) }
Next Stage can be obtained S1+1 (S2 )can be computed by merging from S1 and S11
S2 ={(0,0)(1,2)(2,3)(3,5)}
Include 3rd object
S12 ={ ( 0+5,0+4) (1+5, 2+4)(2+5,3+4) (3+5,5+4) }
= {(5,4)(6,6)(7,7)(8,9)}
24
Next Stage can be obtained S2+1 (S3 )can be computed by merging from S2 and
S12
S3 ={(0,0)(1,2)(2,3)(3,5) (5,4)(6,6)(7,7)(8,9)}
Apply Purging rule
Pairs(3,5) (7,7)(8,9) will be discarded
Therefore ,
S3 ={(0,0)(1,2)(2,3)(5,4)(6,6)}
X=(1,0,1)
25
0/1 KNAPSACK ALGORITHM
Algorithm DKP(p,w,n,m)
{
S0 := {(0,0)};
for i := 1 to n-1 do
{
Si-1 ={(P,W)|(P-pi ,W-wi ) ϵ Si-1 and W <= m);
Si = MergePurge(Si-1 , S1i-1);
26
(PX,WX) = last pair in Sn-1 ;
(PY,WY)=(P1+ pn ,W1+wn ) where W1 is the largest W in any pair in Sn-1 suc
that W+ wn <= m;
// Trace back for xn ,xn-1,…..,x1.
if (PX > PY) then xn = 0;
else xn=1;
TraceBackFor(xn-1,…..,x1);
}
27
COMPLEXITY ANALYSIS
• The complexity of the 0/1 knapsack
algorithm
The complexity of the algorithm is O(n2).
28
29
30
Consider the knapsack instance n = 3, m=50, (w1, w2, w3) = (10,20,30)
& (p1, p2, p3) = (60, 100, 120).
31
SAMPLE QUESTIONS
• Differentiate between fractional knapsack and 0/1 knapsack
• State o/1 knapsack problem
• Consider the knapsack instance n = 3, m=50, (w1, w2, w3) =
(10,20,30) & (p1, p2, p3) = (60, 100, 120).
• Consider the knapsack instance n = 5, m=100, (w1, w2, w3,w4,w5) =
(10,20,30,40,50) & (p1, p2, p3,p4,p5) = (60, 100, 120,140,150).
32
