Advertisement
NabilaShova

coin change-assignmnt

Dec 5th, 2016
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int findMin(int n)
  5. {
  6.     int stamp[n+1];
  7.  
  8.     for(int i=0; i<=n&&i<=6; i++)
  9.     {
  10.         stamp[i] = i;
  11.     }
  12.     if(n>=7)
  13.         stamp[7] = 1;
  14.     if(n>=8)
  15.         stamp[8] = 2;
  16.     if(n>=9)
  17.         stamp[9] = 3;
  18.     if(n>=10)
  19.         stamp[10] = 1;
  20.  
  21.     for(int i=11; i<=n; i++)
  22.     {
  23.         stamp[i] = 1+min( min(stamp[i-1],stamp[i-7]),stamp[i-10] );
  24.     }
  25.     return stamp[n];
  26. }
  27.  
  28. int main()
  29. {
  30.     int n;
  31.     cout<<"Value of Postage: ";
  32.     cin>>n;
  33.     cout<<endl;
  34.  
  35.     int ans = findMin( n );
  36.  
  37.    cout<<"Minimum stamp required: "<<ans<<endl;
  38.     return 0;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement