COMP20007 Design of Algorithms
Dynamic Programming Part 2: Knapsack Problem
Daniel Beck
Lecture 20
Semester 1, 2020
1
The Knapsack Problem
Given n items with
• weights: w1,w2,…,wn • values: v1,v2,…,vn
• knapsack of capacity W
find the most valuable selection of items that will fit in the knapsack.
2
The Knapsack Problem
Given n items with
• weights: w1,w2,…,wn • values: v1,v2,…,vn
• knapsack of capacity W
find the most valuable selection of items that will fit in the knapsack.
We assume that all entities involved are positive integers.
2
Example 2: The Knapsack Problem
Express the solution recursively:
K(i, j) = 0 if i = 0 or j = 0
Otherwise:
K(i, j) =
max(K(i−1,j),K(i−1,j−wi)+vi) ifj≥wi K(i − 1, j) if j < wi
3
{
Example 2: The Knapsack Problem
Express the solution recursively:
K(i, j) = 0 if i = 0 or j = 0
Otherwise:
max(K(i−1,j),K(i−1,j−wi)+vi) ifj≥wi K(i − 1, j) if j < wi
K(i, j) =
For a bottom-up solution we need to write the code that
systematically fills a two-dimensional table.
The table will have n + 1 rows and W + 1 columns.
3
{
Example 2: The Knapsack Problem
function Knapsack(v[1..n], w[1..n], W) for i ← 0 to n do K[i, 0] ← 0
for j ← 1 to W do K[0, j] ← 0
for i ← 1 to n do
for j ← 1 to W do
ifj