[go: up one dir, main page]
Scribd
Upload
20 views15 pages

0-1 Knapsack For Class

This document compares greedy and dynamic programming approaches. It discusses the 0/1 knapsack problem and provides pseudocode for a dynamic programming solution. The dynamic programming approach builds up the optimal solution by considering all subproblems, storing solutions in a two-dimensional table. This runs in O(nW) time, which can be exponential in the worst case if W is very large.

Uploaded by

Perla Dayana Sri Varsha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
20 views15 pages

0-1 Knapsack For Class

This document compares greedy and dynamic programming approaches. It discusses the 0/1 knapsack problem and provides pseudocode for a dynamic programming solution. The dynamic programming approach builds up the optimal solution by considering all subproblems, storing solutions in a two-dimensional table. This runs in O(nW) time, which can be exponential in the worst case if W is very large.

Uploaded by

Perla Dayana Sri Varsha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

Greedy vs Dynamic Programming Approach

•Comparing the methods


•Knapsack problem
•Greedy algorithms for 0/1 knapsack
•An approximation algorithm for 0/1 knapsack
•Optimal greedy algorithm for knapsack with fractions
•A dynamic programming algorithm for 0/1 knapsack
Greedy Approach VS Dynamic Programming (DP)

• Greedy and Dynamic Programming are methods for


solving optimization problems.
• Greedy algorithms are usually more efficient than DP
solutions.
• However, often you need to use dynamic programming
since the optimal solution cannot be guaranteed by a
greedy algorithm.
• DP provides efficient solutions for some problems for
which a brute force approach would be very slow.
• To use Dynamic Programming we need only show that
the principle of optimality applies to the problem.
The 0/1 Knapsack problem

• Given a knapsack with weight W > 0.

• A set S of n items with weights wi >0 and


benefits bi> 0 for i = 1,…,n.

• S = { (item1, w1, b1 ), (item2, w2, b2 ) ,


. . . , ( itemn, wn, bn ) }

• Find a subset of the items which does not exceed


the weight W of the knapsack and maximizes the
benefit.
0/1 Knapsack problem

Determine a subset A of { 1, 2, …, n } that satisfies the


following:

max  bi where  wi  W
iA iA

In 0/1 knapsack a specific item is either selected or


not
Variations of the Knapsack problem

• Fractions are allowed: items can be selected full


with last item included in the solution is either full or
fraction of that item. (like 1,1/2,0)
• No fractions.
– 0/1 (1 brown pants, 1 green shirt…)
– Allows putting many items of same type in
knapsack
• 5 pairs of socks
• 10 gold bricks
Brute force!
• Generate all 2n subsets

• Discard all subsets whose sum of the weights


exceed W (not feasible)
• Select the maximum total benefit of the
remaining (feasible) subsets

• What is the run time?


O(n 2n)
Example with “brute force”

S = { ( item1 , 5, $70 ), (item2 ,10, $90 ), ( item3, 25, $140 ) } , W=25


• Subsets:
1. {} null
2. { ( item1 , 5, $70 ) } Profit=$70
3. { (item2 ,10, $90 ) } Profit=$90
4. { ( item3, 25, $140 ) } Profit=$140
5. { ( item1 , 5, $70 ), (item2 ,10, $90 )}. Profit=$160
6. { (item2 ,10, $90 ), ( item3, 25, $140 ) } exceeds W
7. { ( item1 , 5, $70 ), ( item3, 25, $140 ) } exceeds W
8. { ( item1 , 5, $70 ), (item2 ,10, $90 ), ( item3, 25, $140 ) } exceeds W
Dynamic Programming Approach

• Given a knapsack problem with n items and knapsack


weight of W.

• We will first compute the maximum benefit, and then


determine the subset.

• To use dynamic programming we solve smaller


problems and use the optimal solutions of these
problems to find the solution to larger ones.
Dynamic Programming Approach
• The structure of knapsack problem
– Assume a subproblem in which the set of items is
restricted to {1,…, i } where i  n, and the weight of
the knapsack is w, where 0 w  W.
– Let B [i, w] denote the maximum benefit achieved
for this problem.
– Our goal is to compute the maximum benefit of the
original problem B[n, W]
– We solve the original problem by computing B[i, w]
for i = 0, 1,…, n and for w = 0,1,…,W.
– We need to specify the solution to a larger problem
in terms of a smaller one
A Recursive Solution to knapsack problem

3 cases:
1. There are no items in the knapsack, or the weight of the knapsack
is 0 - the benefit is 0
2. The weight of itemi exceeds the weight w of the knapsack - itemi
cannot be included in the knapsack and the maximum benefit is
B[i-1, w]
3. Otherwise, the benefit is the maximum achieved by either not
including itemi ( i.e., B[i-1, w]),
or by including itemi (i.e., B[i-1, w-wi]+bi)

0 for i  0 or w  0

B[i, w]   B[i  1, w] if w i  w
max{ B[i  1, w], B[i  1, w  w ]  b } otherwise
 i i
Pseudo-code:0/1 Knapsack Problem
Matrix Size: (n+1)*(W+1)
Input: {w1 ,w2, . . . wn }, W , {b1 ,b2, ...b
n }
Output: B[n, W],

for w  0 to W do // row 0
B[0,w]  0
for k  1 to n do // rows 1 to n
B[k, 0]  0 // element in column 0
for w  1 to W do // elements in columns 1 to W
if (wk  w) and (B[k-1, w- wk ] + bk > B[k-1, w])
then B[k, w]  B[k-1, w- wk ] + bk
else B[k, w]  B[k-1, w]
Example:
W = 30, S = { ( i1 , 5, $50 ), (i2 ,10, $60 ), ( i3, 20, $140 ) }

Weight: 0 1 2 3 … 30
MaxProfit { } 0 0 0 0 … 0

Weight: 0 1 2 3 4 5 … 30
MaxProfit { } 0 0 0 0 0 0 … 0
MaxProfit{i1} 0 0 0 0 0 50 … 50
Example continued
W = 30, S = { ( i1 , 5, $50 ), (i2 ,10, $60 ), ( i3, 20, $140 ) }

Weight: 0 ... 4 5 … 9 10 … 14 15 ... 30


MaxProfit { } 0 ... 0 0 … 0 0 … 0 0 … 0
MaxProfit{i1} 0 ... 0 50 … 50 50 ... 50 50 … 50
MaxProfit{i1, i2} 0 … 0 50 … 50 60 … 60 110 … 110

• B[2,10] = max { B[1,10], B[1,10-10] + b2 }


= 60
• B[2,15] = max { B[1,15], B[1,15-10] + b2 }
= max {50, 50+60}
= 110
Example continued
W = 30, S = { ( i1 , 5, $50 ), (i2 ,10, $60 ), ( i3, 20, $140 ) }

Wt: 0...4 5 … 9 10…14 15… 19 20… 24 25…29 30


MaxP{ } 0...0 0 … 0 0 …0 0 … 0 0…0 0… 0 0
MaxP{i1} 0...0 50…50 50…50 50… 50 50…50 50…50 50
MaxP{i1, i2} 0…0 50…50 60…60 110...110 110… 110 ... 110
MaxP{i1,i2,i3} 0…0 50…50 60…60 110...110 140…140 190…190 200

• B[3,20] = max { B[2,20], B[2,20-20] + b3 }


= 140
• B[3,25] = max { B[2,25], B[2,25-20] + 140 }
= max {110, 50+140}
= 190
• B[3,30] = max { B[2,30], B[2,30-20] + 140 }
= 200
Analysis
• It is straightforward to fill in the array using the expression on the
previous slide. SO What is the size of the array??

• The array is the (number of items+1)  (W+1).

• So the algorithm will run in ( n W ). It appears to be linear BUT


the weight is not a function of only the number of items. What if
W= n ! ? Then this algorithm is worst than the brute force method.
One can show algorithms for 0/1 knapsack with worst case time
complexity of O(min ( 2n, n W )) (N169)

• No one has ever found a 0/1 knapsack algorithm whose worst


case time is better than exponential AND no one has proven that
such an algorithm is not possible.

You might also like