This lecture continues to talk about Dynamic Programming, we are going to introduce Knapsack Problem and Fibonacci number problem.

Dynamic Programming

Knapsack Problem

Give ${ n }$ objects and a knapsack

• Item ${ i }$ has integer weight ${ w_i > 0 }$ and value ${ v_i > 0 }$

• Knapsack capacity is ${ W }$

• Goal: Fill the knapsack to maximize the total value.

Here is a example, how knapsack program applied in real world. Like we need to assgin jobs to a machine to maxiniza the total value where the total processing time of the machine is bounded.

PS: in particular, here is a 0-1 knapsack problem, for each item we only have one piece.

Try: Greedy Algorithm

We can try to add items in order as their ratios (${ \frac{v_i}{w_i} }$) if the knapsack still have available capacity

Here is an example,

If we use gready algorithm, we will pick up item ${ {5,2,1 }}$ which’s total value is ${ 35 }$. But the optimal solution is ${ {3,4} }$ and its value is ${ 40 }$.

Dynanmic Programming

If we only have one variable (value), we can not know the what the current weight limit and the weight of the ${ i^{th} }$ item, we can’t decide whether to include item ${ i }$ or not.

So, we use two varible here ${ i \in [1,n] , t\in [1,W] }$

So, we give the Subproblem Definition as follow

• Case 1 OPT does not include item ${ i }$, that means

OPT should maximize the profit on items ${ {1,\cdots, i -1 } }$ with capacity ${ t }$

• Case 2: add item ${ i }$ to knapsack, If ${w_i \leq t }$

OPT should maxm the profit on items ${ {1,\cdots, i -1 } }$ with capacity ${ t -w_1 }$

In summary, (1) if ${ i =0 }$ or ${ t = 0 }$, obviously, the ${ OPT }$ is ${ 0 }$; (2) if ${ w_i > t }$ we have no choice, we have to escape item ${ i }$, that means ${ OPT }$ equals ${ OPT(i-1,t) }$. (3) otherwise, the capacity allow us to consider choosing ${ i }$ or not, we will ${ max \{ OPT(i-1, t), v_i + OPT(i-1,t-w_i) \} }$. Thus we give our “state transition equation”

Pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
13
Knapsack_Problem(n,W,w_1, ... w_n,v_1,...v_n)
    // Initialization
    M: size n*W, the DP matrix where M[i,t] stores OPT(i,w)
    for i = 0 to n:
        for t = 0 to W:
            M[i,t] = 0
    for i = 0 to n:
        for t = 0 to W:
            if (w_i > t)
                M[i,t] = M[i-1,t]
            else
                M[i,t] = max{M[i-1,t],v_i+M[i-1,t-w_i]}
    return M[n,W]

Correctness

The algorithm computes the optimal solution i.e. ${ M[n,W] = OPT(n,W)}$

Proof. We can prove it by induction

Base cases: ${ M(i,0) = 0, M(0,t) = 0, \forall i \in [0,n], t \in [0,W]}$

Induction, ${ M[j,s] = OPT(j,s), \forall j < i, s <t }$, which are all the elements lie in the lower left matrix (based on ${ M[i,t] }$)

• Case 1 ${ w_i > t }$

• Case 2 ${ w_i < t }$

We choose the larger one between adding ${ i }$ or not, which promises the optimal value

QED.

Time and Space complexity

It’s easy to get the space complexity is ${ O(nW) }$ and running time is ${ O(nW) }$. But! It’s not polynomial time. Why? Let’s check the input size (bit size), ${ O (n \lg (v_{max} + w_{max}) + \lg W) }$, we can treat it as ${ O(n \lg W) }$. Thus, compare ${ O(nW) }$ with ${ O(n\lg W) }$. If ${ W }$ dominates, the running time will not be polynomial, so this algorithm is pseudo-polynomial.

Fibonacci number

It’s easy to write down the pseudocode of recursion to get the ${ n^{th} }$ item of sequence.

1
2
3
4
5
Fib(n)
    if n == 1 or 2
        return 1
    else
        return Fib(n-1) + Fib(n-2)

denote the time as ${ T(n) }$, we can write down the recurrence ${ T(n) = T(n-1) + T(n-2) + \theta(1) }$. So, ${ 2T(n-2)+\Theta(1) \leq T(n) \leq 2T(n-1) +\Theta(1)}$, we can guess ${ T(n) = \Omega(2^{n/2}) = O(2^n) }$.

Assume ${ T(n) = \Omega(2^{n/2}) }$, we will prove it by induction.

Base case, ${ T(1), T(2) }$ is trivial.

By induction, ${ T(i) = \Omega(2^{i/2}) ,i<n }$

For ${ T(n) = T(n-1) + T(n-2) + \Theta(1) \geq 2T(n-2) +\Theta(1) = 2 \Omega(2^{(n-2)/2} +\Theta(1) =\Omega(2^{n/2} ) }$

Similarly, we can prove ${ T(n) = O(2^n)}$, so we can get ${ T(n) }$ is exponential running time.

If we use Memorizing Recursion, the running time is ${ O(n) }$.