Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int main()
- {
- int n;
- cin>>n;
- int coin[n],i;
- for(i=0;i<n;i++)cin>>coin[i];
- int taka;
- cin>>taka;
- int tab[taka+1],j=0,mx,track[taka+1];
- tab[0]=0,track[0]=0;
- for(i=1;i<=taka;i++)tab[i]=10000000;
- for(i=1;i<=taka;i++)
- {
- mx=0;
- for(j=0;j<n;j++)
- {
- if(coin[j]>i)continue;
- else
- {
- if(mx<coin[j])
- {
- mx=coin[j];
- track[i]=mx;
- }
- tab[i]=min(tab[i],tab[i-coin[j]]+1);
- }
- }
- }
- //for(i=0;i<=taka;i++)cout<<track[i]<<" ";
- int res[taka+1],k=0;
- i=taka;
- while(i>0)
- {
- res[k++]=track[i];
- i-=track[i];
- }
- cout<<endl<<"amount of coins "<<tab[taka]<<" and coins are"<<endl;
- for(i=k-1;i>=0;i--)cout<<res[i]<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement