Dynamic Knapsack Flashcards
1
Q
As a review, what is the input and definintion of the 0-1 knapsack problem?
A
2
Q
What do we need to output?
How long would it take to brute force?
A
For n different items, the running time is Omega(2n) to brute force
3
Q
Why doesn’t densest first solve the 0-1 integer knapsack problem?
What is the optimal substructure property?
A
4
Q
What is the approach for the dynamic programing 0-1 knapsack problem?
A
5
Q
What is the brute force code for 0-1 dynamic programming knapsack?
A
6
Q
When we are creating our table, what do te subproblems look like?
A
7
Q
What are the table calculations (in general).
Provide the mathematical representation as well
A
8
Q
What is the code for the bottom up tabulation version? And what is the order in which the table is filled out?
A
9
Q
A
