Dynamic Programming in simple words
Why learn knapsack?
Oct 17, 2020
Knapsack
- 01
- Unbounded
Solve problems using knapsack:
2 Coin Problems
Rod cutting problem
Stock Market Max Profit Problem
Max ribbon cut problem
……….
What is DP?
- Overlapping sub problems
- optimal substructure
- 2^n -> m*n
What is Knapsack solution?
- Pick every possible solution to find optimum solution
- Store and use already solved problem results
0/1 Knapsack:
Problem Description:
Solution:
M[n,w] =
if (W[n] = 0) => 0
if (W[n] > w) => M[n-1,w]
Else => max { M[n-1,w], V[n] + T[n-1,w -W[n]] }
Unbounded Knapsack
Variations of Knapsack:
Coin Sum Problem
Is it knapsack? Indication Array of Numbers
Which Knapsack?
Code Variation?
Subset Sum Problem
Rod Cutting Problem
Stock Market Max Profit Problem
Max ribbon cut problem
….
Resources
- Google Doc Presentation to fill tables
https://docs.google.com/presentation/d/1d5u0cmN0u1vjO2b9dYhpMiGvO2wpAN6guOqkSIPs4xU/edit?usp=sharing
- Google Jamboard/Whiteboard
https://jamboard.google.com/d/1yRz4wP1qKr6EQJ8CWWt4G0aoez-aCu-39z4QkIZ8m-w/edit?usp=sharing
- Github Code
https://github.com/vaibhavhajela/AlgorithmsWorkbook
- Algorithm Visualizer to try
https://algorithm-visualizer.org/dynamic-programming/knapsack-problem