Dynamic Programming 2: Knapsack - Chain Multiply Flashcards
Why is an O(nB) knapsack algorithm NOT polynomial time, where n is the number of items and B is the capacity of the knapsack?
Because B is a number. We measure the input size of numbers in bits (since that’s how the computer represents them), and it takes x = log_2 B bits to represent B. Since x is the input size of B and our algorithm is O(B), then in terms of input size it would be O(2^x), since B = 2^x.
Does the greedy approach work for the knapsack problem?
No! The greedy approach commits us to use the optimal solution on each prefix of our items list, but finding the ultimate optimal solution requires that we can combine new items with a suboptimal solution over the prefix.
What should we do if we get a DP solution that uses a two- or three-dimensional table?
See if we can reduce the solution to a one-dimensional table. This is often faster, uses less space, or is at least simpler.
What is the knapsack problem?
Input: n objects with weights W and values V (vectors of length n). Total capacity B (total weight the knapsack can hold).
Goal: Find the set of objects that maximizes total values while meeting the constraint that the sum of all weights < B.
What are the two variants of the knapsack problem?
1) Use at most one copy of each object.
2) Use each object as many times as you want.
What is the chain matrix multiplication problem? (informal)
Given a set of matrices (e.g., A, B, C, and D) and their dimensions, figure out how to chain them together to minimize the cost of computation.
For example, maybe A * (B * (C * D)) uses fewer computations than (A * B) * (C * D).
What is a reasonable cost to use for the chain matrix multiplication problem?
Given two matrices W (size a x b) and Y (size b x c), multiplying them will require abc element multiplications and ac(b-1) additions. So abc is a reasonable cost to use.
What is the chain matrix multiplication problem? (formal)
Given n matrices A_1, …, A_n where each matrix A_i has dimensions m_(i-1) x m_i
Input: m_0, …, m_n
Goal: What is the minimum cost of computing A_1 * … * A_n
What is the “trick” to solving the chain matrix multiplication problem?
Use substrings instead of just prefixes/suffixes!
When devising subproblem, try a prefix of the input first. If this doesn’t work, try what? And if that works, what is a good next step?
Substring! Once you have a valid solution using a substring, go back and see if you really needed it: maybe in hindsight there is a faster algorithm that actually works on prefixes.
