PROBLEM STATEMENT:
We are given an array of coins (containing the value of coins which we are allowed to use with infinity number of each type of coins) and a sum (simply a large note[Indian currency] in real life) . We have to determine what is the minimum number of coins that can give total sum as the value of the note.
STEPS:
1. We are taking n, sum, a[n] , size of array of coins, value of the note, array of coins as input respectively.
2. Now, we are taking one table of size (n+1)*(sum+1) to store minimum number of coins for each conditions less than the given conditions of size of array and value of note, starting from size of array=0 and value of note =0.
3. Now, we are considering two loops to fill up the table, where i represents the size of array and j represents the value of note i.e. sum.
3. Now, we can observe that if the value of note i.e. the given sum=0, then minimum number of coins required is zero. Also, if the size of array is zero i.e. there is no coins given, then it is impossible to make change of the note, so we will initialize the minimum number of coins required as INT_MAX-1.
4. When the size of the array is 1, then there two possibilities, either we will take the first element of the array or we will not. If the first element divides the sum i.e. j%a[0]==0, then we can initialize the minimum required coin as sum divided by the first element, i.e. j/a[0]. If the first element doesn't divide the sum, i.e. j%a[0]!=0, then there is no possible way of making change, so we will initialize the minimum number of coins required as INT_MAX-1.
5. Now, if any coin has a value less than or equal to the sum, then there are two possibilities either we will take the coin or we will not. If we take the coin, the number of coins taken will increase by 1. To get the minimum value, we have to take the minimum value of the above two possibilities.
6. If the value of coin is greater than sum, we will just exclude the coin.
CODE:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,sum;
cin>>n>>sum;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int dp[n+1][sum+1];
for(int i=0;i<n+1;i++)
{
for(int j=0;j<sum+1;j++)
{
if(j==0)
dp[i][j]=0;
else if(i==0)
dp[i][j]=INT_MAX-1;
else if(i==1)
{
if(j%a[i-1]==0)
dp[i][j]=j/a[i-1];
else
dp[i][j]=INT_MAX-1;
}
else if(a[i-1]<=j)
dp[i][j]=min(1+dp[i][j-a[i-1]],dp[i-1][j]);
else if(a[i-1]>j)
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][sum];
return 0;
}
5 6
1 2 3 4 5
OUTPUT:
2
The possible ways are
1+1+1+1+1+1
1+1+1+1+2
1+1+1+3
1+1+2+2
1+1+4
1+5
1+2+3
2+2+2
2+4
3+3
So, the minimum number of ways required is 2.
0 Comments