2023-10-16

Introduction

Summary

keywords

TODO

HW

Exercise*

Next time

---

Recap

Knapsack

---

0/1 Knapsack Tabulation

Fill out the table one by one, fully.

Initialization : first row, first column is zero.

When you need a {0,1,0,1, ..} format result, you should do backtracking. Compare with the adjacent subproblem results and guess if the item is picked. If the $P(i-1,W) < P(i,W)$ , the $i^{th}$ element is picked in calculating $P(i,W)$.

Now consider $P(i-1,W-W_i)$ and do the similar comparison to find if $(i-1)^{th}$ element is picked.

reminder Recursion has 3 steps.

1. base case (smallest valid input)

2. hypothesis (of decreasing an input)

3. Induction

Principle of Optimality means that the algorithm gives result of "sequence of decisions" to the optimality. With that result, we can draw a choice diagram.

0/1 Knapsack Recursion

#todo : fill out.

0/1 Knapsack Memoization

Calculate only what you need, and store it for future demands.

Decide the table size. initialize with unreachable value.

Check if the subproblem is already computed. Store each result in the table, and next time refer it .

0/1 Knapsack Recursion to Tabulation

Steps .

1. initialization of first row and first column.

2. Fill each row and each column, one by one.

Time Complexity of 0/1 Knapsack Problem

1. Recursion (Brute force)

since the sequence follows a pick-or-no-pick decision diagram, $O(2^n)$.

#todo : write the recurrence relation.

2. Tabulation

filling out the full table. $O(nW)$ linear time complexity.

How do you compare which time complexity is higher, simply take a log.

---

Unbounded Knapsack

You can take an item several times.

How will the choice diagram change?

1. compare weight of the biggest weight and the capacity

2. For subproblems, you do not decrease the item number.

3. The item number will only decrease if the capacity is smaller than the biggest weight.

4. If you choose to pick the item, you still leave the possibility to pick the item in the subproblem again.

5. It you do not choose to pick the item, you do not pick the item ever again later.

Only one part is changed in the algorithm (from 0/1 algorithm )

Similar problem : divide the rod.