-
Notifications
You must be signed in to change notification settings - Fork 30
/
Copy pathMinimizing Coins.cpp
109 lines (86 loc) · 2.99 KB
/
Minimizing Coins.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/*
Solution by Rahul Surana
***********************************************************
Consider a money system consisting of n coins. Each coin has a positive integer value.
Your task is to produce a sum of money x using the available coins in such a way that the number of coins is minimal.
For example, if the coins are {1,5,7} and the desired sum is 11, an optimal solution is 5+5+1 which requires 3 coins.
Input
The first input line has two integers n and x: the number of coins and the desired sum of money.
The second line has n distinct integers c1,c2,…,cn: the value of each coin.
Output
Print one integer: the minimum number of coins. If it is not possible to produce the desired sum, print −1.
***********************************************************
*/
#include <bits/stdc++.h>
#define ll long long
#define vl vector<ll>
#define vi vector<int>
#define pi pair<int,int>
#define pl pair<ll,ll>
#define all(a) a.begin(),a.end()
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define FOR(i,a) for(int i = 0; i < a; i++)
#define trace(x) cerr<<#x<<" : "<<x<<endl;
#define trace2(x,y) cerr<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<endl;
#define trace3(x,y,z) cerr<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<" | "<<#z<<" : "<<z<<endl;
#define fast_io std::ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
using namespace std;
int MOD=1e9+7;
// vector<ll> dp;
// int df(vector<int> &ar,int n, int x){
// queue<int> q;
// map<int,bool> v;
// q.push(0);
// int c = 0;
// while(!q.empty()){
// int size = q.size();
// while(size--){
// int z = q.front();
// q.pop();
// if(v[z]) continue;
// v[z] = true;
// if(z > x) continue;
// if(z==x) return c;
// for(int i = 0; i < ar.size(); i++){
// if(z+ar[i]<=x)
// q.push(z+ar[i]);
// }
// }
// c++;
// }
// return -1;
// }
int main() {
fast_io;
int t=1,w = 1;
// cin >> t;
while(t >= (w)){
ll n,x;
cin >> n>>x;
vector<int> ar(n);
FOR(i,n) cin >> ar[i];
sort(ar.begin(),ar.end());
vector<int> dp(x+1,1e9);
for(int i = 0; i < x+1; i++){
if(i%ar[0] == 0){
dp[i] = i/ar[0];
}
}
for(int i = 1; i < n;i++){
vector<int> temp(x+1,1e9);
for(int j = 0; j < x+1; j++){
temp[j] = dp[j];
if(j-ar[i] >= 0)
temp[j] = min(1+temp[j-ar[i]],temp[j]);
}
dp = temp;
}
cout << (dp[x] == 1e9? -1:dp[x]) <<"\n";
// cout << "Case #" << w << ": " << ans <<"\n";
w++;
}
}