Introduction
Summary
keywords
TODO
HW
Exercise*
Next time
Recap
DP
Why need? For optimization problems Hint? overlapping subproblems difference from divide n conquer? divide n conquer problem are disjoint (never-repeated) problems. follows principle of optimality
strategy 1. memoization. We save the function results on arrays. strategy 2. tabulation. Completely remove the recursion.
Knapsack Problem
#1. 0/1 Knapsack problem.
similar problems : subset sum equal sum partition count of sldfksmd. #todo : fill out the list.
Choose or don't choose How many solutions could be there? $2^n$ DP should check each and every solution candidate.
DP => Recursion -> memoization -> tabulation
Strategy 1) Tabulation
what should be the size of the matrix? hint is in the problem's numeral condition. the problem picks from n objects, and k is the capacity of the bag. So, the matrix should be $(n+1)*(k+1)$ size. row is the number of candidate items.
Each cell represents for net profit. Each cells are the subproblems. ex. for 3rd row 5th column, the cell value is the max profit when we pick 3 items in total and capacity is 5.
initialize 0 row 0 column with 0. Why need 0 row 0 column? we should think of the 0 capacity. base case.
Tabulation method) for each cell, how do we fill out?
-
for capacity smaller than the heaviest object, The heaviest object cannot be chosen. It is the same problem with the upper row.
-
for capacity bigger than the sum of every object, we can take all the items, so the net profit is the sum of all profit.
-
for capacity in between, check if taking the heaviest item $A$ is efficient. To do so, compare $P_A+P(n-1,k-W_A)$ and $P(n-1,k)$
#2. Unbounded Knapsack
similar problems: rod cutting
can choose the identical items several times add multiple occurances of the same object
#3. Fractional Knapsack
Suitable for greedy.
can take the fraction of an object.