Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- using namespace std;
- int M[100];
- int S[100];
- int sum(int c[], int n, int coinSize){
- if(M[n] == -1){
- int minval=9999, coinval =-1;
- for(int i=0; i<coinSize; i++){
- if(c[i]<=n){
- int tval = 1+sum(c, n-c[i],coinSize);
- if(tval<minval) {
- minval = tval;
- coinval = c[i];
- }
- }
- }
- M[n] = minval;
- S[n] = coinval;
- }
- return M[n];
- }
- int main() {
- M[0]=0;
- for(int i=1; i<100; i++)
- M[i]=-1;
- int coins[]= {2,4,5,6,8};
- //x = how many want you take input
- //for(i=0; i<x){
- //take input coins[i]
- //}
- int coinSize = 5; //arraysize
- int n=0;
- int result = sum(coins, n, coinSize);
- if(result == 9999){
- cout<<"False"<<endl;
- }
- else if(result == 0){
- cout<<"True {}"<<endl;
- }
- else{
- cout<<"True{";
- int end = n;
- while(end !=0 ){
- cout<<S[end]<<",";
- //cout<<S[end]<<" ";
- end -=S[end];
- }
- cout<<"}";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement