how to check weather it is DP probelm or not?
- First property there will be always a choice like Y/N
- Ask will to find optimal like max, min, largest etc.
- And there will be always posibitly of recursion
I1, I2, I3, I4
Weight {W1, W2, W3, W4}
Cost {C1, C2, C3, C4}
Max Bag weight - W
Ask is Max Profit?
Knapsack problem is always of three category
- Fractional Knapsack (Greedy) - weight can be fractional
- 0/1 Knapsack - weight can not be fractional and it is bounded means you can take whole item
- Unbounded knapsack - unlimited supply of items
- Subset Sum Problem
- Equal Sum problem
- Count of subset sum
- Minimum subset sum difference
- Target Sum