Dynamic Knapsack Flashcards
As a review, what is the input and definintion of the 0-1 knapsack problem?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/163/671/a_image_thumb.png?1553627074)
What do we need to output?
How long would it take to brute force?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/163/778/q_image_thumb.png?1553627128)
For n different items, the running time is Omega(2n) to brute force
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/163/778/a_image_thumb.png?1553627159)
Why doesn’t densest first solve the 0-1 integer knapsack problem?
What is the optimal substructure property?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/163/856/a_image_thumb.png?1553627249)
What is the approach for the dynamic programing 0-1 knapsack problem?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/163/988/a_image_thumb.png?1553627341)
What is the brute force code for 0-1 dynamic programming knapsack?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/164/432/a_image_thumb.png?1553628302)
When we are creating our table, what do te subproblems look like?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/167/756/a_image_thumb.png?1553630180)
What are the table calculations (in general).
Provide the mathematical representation as well
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/167/940/a_image_thumb.png?1553630776)
What is the code for the bottom up tabulation version? And what is the order in which the table is filled out?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/168/779/a_image_thumb.png?1553631387)