Advertisement
jakaria_hossain

Coin change

Oct 23rd, 2018
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.95 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5. int n;
  6. cin>>n;
  7. int coin[n],i;
  8. for(i=0;i<n;i++)cin>>coin[i];
  9. int taka;
  10. cin>>taka;
  11. int tab[taka+1],j=0,mx,track[taka+1];
  12. tab[0]=0,track[0]=0;
  13. for(i=1;i<=taka;i++)tab[i]=10000000;
  14. for(i=1;i<=taka;i++)
  15. {
  16. mx=0;
  17. for(j=0;j<n;j++)
  18. {
  19. if(coin[j]>i)continue;
  20. else
  21. {
  22. if(mx<coin[j])
  23. {
  24. mx=coin[j];
  25. track[i]=mx;
  26. }
  27. tab[i]=min(tab[i],tab[i-coin[j]]+1);
  28. }
  29. }
  30. }
  31. //for(i=0;i<=taka;i++)cout<<track[i]<<" ";
  32. int res[taka+1],k=0;
  33. i=taka;
  34. while(i>0)
  35. {
  36. res[k++]=track[i];
  37.  
  38. i-=track[i];
  39. }
  40. cout<<endl<<"amount of coins "<<tab[taka]<<" and coins are"<<endl;
  41. for(i=k-1;i>=0;i--)cout<<res[i]<<endl;
  42. return 0;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement