DP is enhanced recursion.
Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems. s. A dynamic-programming algorithm solves each subproblem just once and then saves its answer in a table, thereby avoiding the work of re computing the answer every time it solves each subproblem. It is either done using top down or bottom up approach.
To solve the original problem of size n, we solve smaller problems of the same type, but of smaller sizes
HOW TO IDENTIFY IF A QUESTION IS FROM DYNAMIC PROGRAMMING?
1. All points related to recursion. If two functions are being called inside the recursive code, then it is a DP problem.
2. Asked for a optimal solution (minimum, maximum, largest, smallest etc) where you will be given a number of choices. There are many possible solutions to the problem, but you need to find only the optimal one.
RELATED QUESTIONS:
1. O-1 Knapsack
2. Unbounded Knapsack.
3. Fibonacci
4. LCS
5. LIS.
6. Kadane's algorithm.
7. Matrix chain multiplication.
8. DP on tress.
9. DP on grid.
KNAPSACK:
1. Fractional Knapsack.
2. 0-1 Knapsack.
3. Unbounded Knapsack.
Knapsack can be taken as a bag and we will be given a number of items. We will be given a value(price) array and a weight array of the items given. And the maximum capacity of the bag is given i.e. the maximum weight it can hold. We will have to determine the maximum price or value or profit the bag can hold. We have the choices of the items.
In fractional Knapsack, we are allowed to divide an item so as to fit into the bag, but in 0-1 Knapsack, we are not allowed to divide. Fractional Knapsack can be solved using greedy.
In unbounded Knapsack, we have unlimited amount of the same item i.e. we can choose an item infinity number of times if we want.
0-1 KNAPSACK:
RECURSIVE CODE:
#include <bits/stdc++.h>
using namespace std;
int knapsack(int n,int wt[], int v[],int w)
{
if (n==0 || w==0) //base condition, if either n is zero or weight is zero
return 0;
if(wt[n-1]<=w)
return max((v[n-1] + knapsack(n-1,wt,v,w-wt[n-1])),(knapsack(n-1,wt,v,w)));
// will take the maximum output of including the current item and not including the current item.
else if(wt[n-1]>w)
//If the weight of the item is greater than the weight of the knapsack, we will not include the item and will jump to the next item.
return knapsack(n-1,wt,v,w)
}
int main()
{
int wt[5]={1,5,9,6,4};
int v[5]={1,3,2,4,5};
int n=5,w=10;
int profit=knapsack(n,wt,v,w);
cout<<profit;
return 0;
}
OUTPUT: 9
MEMOIZATION:
In Memoization, we simply improve the recursive code by storing the elements in a matrix to use it in future, so that in some steps we don't have to call the recursive function. For this purpose, we take a matrix to store the elements.
CODE:
#include <bits/stdc++.h>
using namespace std;
int dp[102][1002];
int knapsack(int n,int wt[], int v[],int w)
{
if (n==0 || w==0)
return 0;
if(dp[n][w]!=-1)
return dp[n][w];
if(wt[n-1]<=w)
return dp[n][w]=max((v[n-1] + knapsack(n-1,wt,v,w-wt[n-1])),(knapsack(n-1,wt,v,w)));
else if(wt[n-1]>w)
return dp[n][w]=knapsack(n-1,wt,v,w);
}
int main()
{ memset(dp,-1,sizeof(dp));
int wt[5]={1,5,9,6,4};
int v[5]={1,3,2,4,5};
int n=5,w=10;
int profit=knapsack(n,wt,v,w);
cout<<profit;
return 0;
}
NUMBER OF SUBSET WITH GIVEN DIFFERENCE
UNBOUNDED KNAPSACK:
The number of each items is infinite, i.e. unbounded. We can include any item multiple number of items.
CODE:
https://www.cuplex2b.com/2021/01/coin-change-problem.html
https://www.cuplex2b.com/2021/01/coin-change-problem-ii-minimum-no-of.html
0 Comments