CS计算机代考程序代写 algorithm COMP20007 Design of Algorithms

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: { K(i, j) = max(K(i−1,j),K(i−1,j−wi)+vi) ifj≥wi K(i − 1, j) if j < wi 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