Yeah! There are hell lot of dynammic programming problems which can solved by some slight modifications of 0/1 Knapsack Problem.
Some of related Problems:
What is 0/1 Knapsack problem?
Answer: We contain a bag which can hold a specific amount of weight and there are collection of items with a specified weight andprofit / valueassociated to it . You have to choose a combinations of items in such a way that whose sum of weight should not exceed the bag capacity and with maximum profit gain.
Makes sense!
**How can we solve this problem? **
We have to solve this by maintaining a 2D matrix!
Data about 2D matrix:
- Rows - Total Capacity.
- Cols - Number of items available ( Generally the array elements)
What does a cell in a 2D matrix signifies?
Answer: Lets consider cell with row - w and col - i, A cell in the matrix signifies the profit gained by carring items from 0 to i and the capacity of the bag to be w.
What are the base cases?
Answer: If the capacity of the bag is 0 or the # of items to be carried is 0, the profit gained would be 0.
What are the states of DP
If you don't know what state is? State are the variables used to identify a subproblem! (PS : Its my own definition)
Here is a more detailed one!
State Definition
Answer: Weight and Items
Decisions to be taken
Answer: There are two decisions whether to include the item or not.
I am beginner in understanding DP! So please correct me if i am wrong!