#include<bits/stdc++.h>
#define speed ios_base :: sync_with_stdio(false);cin.tie(NULL)
using namespace std;
bool compare(int A, int B)
{
return (A > B);
}
int coin(vector<int>v, int t)
{
if(t == 0)
return 0;
int result = INT_MAX;
for(int i=0;i<v.size();i++)
{
if(v[i] <= t)
{
int sub_result = coin(v, t-v[i]);
if(sub_result != INT_MAX && sub_result + 1 < result)
result = sub_result + 1;
}
}
return result;
}
int main()
{
int n, i, tm;
cout << "Enter Total Coin Number :: ";
cin >> n;
vector<int>v(n);
cout << "Enter Coins Amount :: " << "\n";
for(i=0;i<n;i++)
cin >> v[i];
cout << "Enter Total Amount :: ";
cin >> tm;
sort(v.begin(),v.end(), compare);
cout << "Minimum Coin Required :: " << coin(v, tm) << "\n";
return 0;
}
#define speed ios_base :: sync_with_stdio(false);cin.tie(NULL)
using namespace std;
bool compare(int A, int B)
{
return (A > B);
}
int coin(vector<int>v, int t)
{
if(t == 0)
return 0;
int result = INT_MAX;
for(int i=0;i<v.size();i++)
{
if(v[i] <= t)
{
int sub_result = coin(v, t-v[i]);
if(sub_result != INT_MAX && sub_result + 1 < result)
result = sub_result + 1;
}
}
return result;
}
int main()
{
int n, i, tm;
cout << "Enter Total Coin Number :: ";
cin >> n;
vector<int>v(n);
cout << "Enter Coins Amount :: " << "\n";
for(i=0;i<n;i++)
cin >> v[i];
cout << "Enter Total Amount :: ";
cin >> tm;
sort(v.begin(),v.end(), compare);
cout << "Minimum Coin Required :: " << coin(v, tm) << "\n";
return 0;
}
Comments
Post a Comment