SC2001 Lab3

Dynamic Programming

We have a knapsack of capacity weight $C$ (a positive integer) $n$ types of objects. Each object of the ith type has weight $w_i$ and profit $p_i$
(all $w_i$ and all $p_i$ are positive integers, $i = 0, 1, …, n-1$).
There are unlimited supplies of each type of objects.
Find the largest total profit of any set of the objects that fits in the knapsack.

Part 1

Give a recursive definition of the function $P(C)$.

Give a recursive definition of the function $P(C)$.

$P(0) = 0$ Base Case

Give a recursive definition of the function $P(C)$.

$P(0) = 0$ Base Case

$P(C) = \sum_{i=0}^{n} {max(p_i + P(C-w_i),P(C))}$ when $C-w_i \geq 0$

Part 2

Draw the subproblem graph for P(14) where n is 3

Draw the subproblem graph for P(14) where n is 3

Draw the subproblem graph for P(14) where n is 3

We can see that there are a lot of redundant calls
for example we call P(0) 3 times.

Part 3

Give a dynamic programming algorithm to compute the maximum profit, given a knapsack of capacity C, n types of objects with weights $w_i$ and profits $p_i$ using the bottom up approach.

dp[i][j] mean maximum profit of bag capacity j after considering i objects.

dp[i][j] = dp[i-1][j] means we don't take object i into our bag
dp[i][j] = dp[i][j-w[i]]+p[i] means we take object i into our bag if w[i] $\leq$ j

Can we optimize it ?

Memory optimization
Memory optimization

We convert from 2 dimensional array to 1 dimension,
since only current state that need for computation.
Therefore the memory is reduce from O(nC) to O(C)

Part 4

Part A

$w[i] = {4,6,8}$

$p[i] = {7,6,9}$

Part A

$w[i] = {4,6,8}$

$p[i] = {7,6,9}$

result = 21

Part B

$w[i] = {5,6,8}$

$p[i] = {7,6,9}$

Part B

$w[i] = {5,6,8}$

$p[i] = {7,6,9}$

result = 16

Thank you