Scribd
Upload
2 views42 pages

Knapsack Algorithm

The document discusses the 0-1 Knapsack problem, which involves maximizing the value of items placed in a knapsack with a given weight capacity, without allowing fractions of items. It outlines the algorithm's dynamic programming approach, including base cases and a time complexity of O(n*W). Additionally, it compares this method to a brute force approach that examines all possible subsets of items.

Uploaded by

jaycolon021
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
2 views42 pages

Knapsack Algorithm

The document discusses the 0-1 Knapsack problem, which involves maximizing the value of items placed in a knapsack with a given weight capacity, without allowing fractions of items. It outlines the algorithm's dynamic programming approach, including base cases and a time complexity of O(n*W). Additionally, it compares this method to a brute force approach that examines all possible subsets of items.

Uploaded by

jaycolon021
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/ 42

CMSC 142

 Given a knapsack with maximum


capacity W, and a set S consisting of n
items
 Each item i has some weight wi and
benefit value bi (all wi and W are
integer values)
W = < Capacity >

V1 = ? V2 = ? V3 = ? V4 = ?
W1 = ? W2 =? W3 =? W4 =?
The goal is to maximize the value
of a knapsack that can hold at
most W units (i.e. lbs or kg) worth
of goods from a list of items I0, I1, …
In-1.
The difference between this problem and
the fractional knapsack one is that you
CANNOT take a fraction of an item.

• You can either take it or not.


• Hence the name Knapsack 0-1
problem.
 Base Case 1: When the knapsack
capacity is = 0 . Then there are 0 items
that you can place in the knapsack.

 Base Case 2: When the number of items


to be placed = 0 . Then there are 0 items
that you can place in the knapsack.
for w = 0 to W // Initialize 1st row to 0’s
V[0,w] = 0
for i = 1 to n // Initialize 1st column to 0’s
V[i,0] = 0
for i = 1 to n
for w = 0 to W
if wi <= w // item i fits

if bi + V[i-1,w-wi] > V[i-1,w] // item previous sub


problem is better/ retain
V[i,w] = bi + V[i-1,w- wi]

else // item in previous sub problem is better/ retain


V[i,w] = V[i-1,w]

else V[i,w] = V[i-1,w] // wi > w , retain


for w = 0 to W O(W)
V[0,w] = 0
for i = 1 to n
V[i,0] = 0
for i = 1 to n
for w = 0 to W
Repeat n times
< the rest of the code > O(W)

What is the running time of this algorithm?


O(n*W)
 Brute Force
• The naïve way to solve this problem is to
cycle through all 2n subsets of the n items
and pick the subset with a legal weight that
maximizes the value of the knapsack.
W = < Capacity >

V1 = ? V2 = ? V3 = ? V4 = ?
W1 = ? W2 =? W3 =? W4 =?
I = 4 ( # of
items) W=6
W = 6 (Max
weight)

V1 = 3 V2 = 2 V3 = 4 V4 = 4
W1 =4 W2 =3 W3 =2 W4 =3
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

1
2d Array
2

4
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Base Case 1: 1 0

Base Case 2:
2 0
3 0
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Item 1 cannot fit on the
given instance
1 0 0

w1 > W
2 0
3 0
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Item Fits on capacity 1 0 0 0 0 3
compare current value with
cell above
2 0
3 0
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Weight residue allows 1
more unit 1 0 0 0 0 3 3
Check previous row for 2 0
item that can fit
3 0
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0

Weight residue allows 2


1 0 0 0 0 3 3 3
more unit
2 0
3 0
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
1 0 0 0 0 3 3 3
3rd row (subproblem)
2 0 0 0
3 0
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
1 0 0 0 0 3 3 3
2nd item fits on capacity
2 0 0 0 2
3 0
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0

compare current value with


1 0 0 0 0 3 3 3
cell above
2 0 0 0 2 3
3 0
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
1 0 0 0 0 3 3 3
2 0 0 0 2 3 3
3 0
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
1 0 0 0 0 3 3 3
4th row (subproblem)
2 0 0 0 2 3 3 3
3 0 0
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
1 0 0 0 0 3 3 3
2 0 0 0 2 3 3 3
3 0 0 4
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0

Compare value to cell


1 0 0 0 0 3 3 3
above
2 0 0 0 2 3 3 3
3 0 0 4 4
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0

Compare value to cell


1 0 0 0 0 3 3 3
above
2 0 0 0 2 3 3 3
3 0 0 4 4 4
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Compare value to cell
above 1 0 0 0 0 3 3 3
You can fit another item
from the previous row to
2 0 0 0 2 3 3 3
your bag
3 0 0 4 4 4 6
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Compare value to cell
above 1 0 0 0 0 3 3 3
You can fit another item
from the previous row to
2 0 0 0 2 3 3 3
your bag
3 0 0 4 4 4 6 7
4 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
1 0 0 0 0 3 3 3
5th row (subproblem)
2 0 0 0 2 3 3 3
3 0 0 4 4 4 6 7
4 0 0
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Compare value to cell 1 0 0 0 0 3 3 3
above
2 0 0 0 2 3 3 3
3 0 0 4 4 4 6 7
4 0 0 4
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Compare value to cell 1 0 0 0 0 3 3 3
above
2 0 0 0 2 3 3 3
3 0 0 4 4 4 6 7
4 0 0 4 4
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Compare value to cell 1 0 0 0 0 3 3 3
above
2 0 0 0 2 3 3 3
3 0 0 4 4 4 6 7
4 0 0 4 4 4
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Compare value to cell
above
1 0 0 0 0 3 3 3

You may fit another item


2 0 0 0 2 3 3 3
3 0 0 4 4 4 6 7
4 0 0 4 4 4 8
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Compare value to cell
above
1 0 0 0 0 3 3 3

You may fit another item


2 0 0 0 2 3 3 3
3 0 0 4 4 4 6 7
4 0 0 4 4 4 8 8
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
1 0 0 0 0 3 3 3
Optimal Value = 8
2 0 0 0 2 3 3 3
3 0 0 4 4 4 6 7
4 0 0 4 4 4 8 8
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
Now to find out which items
are used in the optimal
1 0 0 0 0 3 3 3
value
(optimal items)
2 0 0 0 2 3 3 3
3 0 0 4 4 4 6 7
4 0 0 4 4 4 8 8
1. Start of from the optimal value
2. Check Where the cellvalue has been
derived
1. If the item is derived from the previous sub-
problem the current item is NOT part of the
optimal
2. If not derived, it is an optimal item and update the
the residue of the knapsack capacity based on the
current item’s weight
3. Continue till you reach zero
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

• If cell is derived from


the previous sub 0 0 0 0 0 0 0 0
problem the item is not
part of the optimal. 1 0 0 0 0 3 3 3
• If not, it is part of the 2 0 0 0 2 3 3 3
optimal and account the
weight of the item on the 3 0 0 4 4 4 6 7
total capacity remaining
4 0 0 4 4 4 8 8
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0

• Keep repeating until you


1 0 0 0 0 3 3 3
touch zero
2 0 0 0 2 3 3 3
3 0 0 4 4 4 6 7
4 0 0 4 4 4 8 8
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0

• Keep repeating until you


1 0 0 0 0 3 3 3
touch zero
2 0 0 0 2 3 3 3
3 0 0 4 4 4 6 7
4 0 0 4 4 4 8 8
v1 = 3 v2 = 2 v3 = 4 v4 = 4
w1 = 4 w2 = 3 w3 = 2 w4 = 3
W=6

i/w 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0
• Optimal items include: 1 0 0 0 0 3 3 3
Items 3
Items 4
2 0 0 0 2 3 3 3
3 0 0 4 4 4 6 7
4 0 0 4 4 4 8 8
 Dynamic programming is a useful technique of solving
certain kind of problems

 When the solution can be recursively described in


terms of partial solutions, we can store these partial
solutions and re-use them as necessary (memorization)

 Running time of dynamic programming algorithm vs.


naïve algorithm:

• 0-1 Knapsack problem: O(W*n) vs. O(2n)


if (item fits)
if ((item_value + residue_value) > cell_value_above)
use item_value + residue_value

else
use cell_value_above

else
use cell_value_above

You might also like