Week 9 - Dynamic Programming

Question 1

What is dynamic programming

Answer 1

Dynamic programming is a method for solving complex problems by breaking them down into simpler overlapping subproblems, solving each subproblem once, and storing their solutions to avoid redundant computations.

Question 2

How does dynamic programming work, step by step?

Answer 2

Here’s how dynamic programming works, explained step by step:

1. Initialize a Grid: Start with an empty grid where rows represent items and columns represent sub-wallet sizes.
2. Fill the First Row: For each cell in the first row, determine if the first item fits into the sub-wallet. If it fits, place the item’s value in that cell.
3. Move to the Next Row: For each subsequent item (row), check if it fits into each sub-wallet size (column). If it doesn’t fit, retain the previous value. If it fits, compare the value of including the item with the current best and update the cell accordingly.
4. Combine Values: When an item fits and leaves extra space, add the best value from the remaining space to maximize the total value.
5. Repeat Until Complete: Continue this process until all items and sub-wallet sizes are considered, filling in the grid to reflect the best possible value at each step.

Question 3

How does dynamic programming solve the knapsack problem?

Answer 3

Dynamic programming solves the knapsack problem by starting with smaller “sub-knapsacks” and progressively building up to the original problem. It uses a grid where rows represent items and columns represent knapsack sizes, filling in the grid with sub-knapsack values step by step. By solving these smaller sub-problems first, the algorithm efficiently calculates the optimal value for the full knapsack.

Question 4

Can you add more items to the knapsack after solving the problem?

Answer 4

Yes! But new maximum values need to be calculated. Dynamic programming will continue to build on the existing grid to update the solution.

Question 5

Can you change the order of the rows in the dynamic programming grid?

Answer 5

Yes! Changing the order of the rows has no effect on the outcome, as the row order doesn’t matter.

Question 6

Can you fill the grid column-wise instead of row-wise in dynamic programming?

Answer 6

For this problem, it works, but it may not be effective for others.

Question 7

Can you add an item with a smaller size to the knapsack?

Answer 7

Yes! However, you would likely need to recompute the entire grid to account for the new item.

Question 8

Does dynamic programming handle splitting items (and their values)?

Answer 8

No! Dynamic programming only works for whole items. But a greedy algorithm would work!

Question 9

Can dynamic programming handle items that depend on each other?

Answer 9

No, dynamic programming only works when each subproblem is discrete and does not depend on other subproblems.