uva 166 - Making Change

  1 /*
  2  Problem link
  3  Type: DP
  4  Algorithm:
  5      The d(i,j) array gives the minimum number of coins to make up i$ from
  6          coins[1..j] with infinite number of each coin type.
  7      The f(i,j,k) array gives the minimum number of coins to make up i$ from
  8          coins[1..j] with the number of coins[j] doesnt exceed k.
  9      The a(i) array is the number of coins of each type.
 10      First calculate d(i,j) using the coin change problem.
 11      * Find f(i,j,k):
 12      -f(0,j,k) = 0 for all j from 1 to 6 and k from 0 to a[j]: There is zero coin
 13      to made up 0$
 14      -f(i,j,0) = f(i,j-1,a[j-1]): If the number of coin[j] not exceed 0 means
 15      there are no coin[j], hence it is f(i,j-1,a[j-1]): the number of coins
 16      from coin[1..j-1] with coin[j-1] not exceed a[j-1].
 17      -Now if we decide not to choose the kth coin[j], then the number of coin
 18      is f(i,j,k-1) for all k>=1. Else it would be f(i-coin[j],j,k-1)+1 if we
 19      decide to choose the kth coin[j] (of course coin[j] must less than or equal
 20      to i).
 21      -Therefore: f(i,j,k) = min(f(i,j,k-1),f(i-coin[j],j,k-1)+1) if coin[j]<=i
 22                  else f(i,j,k) = f(i,j,k-1)
 23  
 24      But the f array should calculate to a number i somewhere larger than n,
 25      for example: n = 5, I will calculate to 5*n = 25. The reason is we can
 26      pay larger than the price and take the money in return, for example n = 95,
 27      we pay 100 and take 5 in return. If we pay larger, then the number of coins
 28      is f(i,j,k)+d[i-n,6]. So initially, we pay exactly the price f(n,6,a[6])
 29      and we run from there to 5*n to take the optimal result.
 30  */
 31  #include <iostream>
 32  #include <cstdio>
 33  #include <cstdlib>
 34  #include <cstring>
 35  #include <cmath>
 36  #include <iomanip>
 37  using namespace std;
 38  
 39  const int maxn = 2000;
 40  const int coins[7] = {0,1,2,4,10,20,40};
 41  const double eps = 1E-9;
 42  
 43  void maked();
 44  void makef(int);
 45  
 46  int d[maxn][10];
 47  int f[maxn][10][251];
 48  int a[7];
 49  double n;
 50  
 51  int main()
 52  {
 53      maked();
 54      while (true)
 55      {
 56          int sum = 0;
 57          for (int i=1; i<=6; i++)
 58          {
 59              cin >> a[i];
 60              sum+=a[i];
 61          }
 62          if (sum==0) break;
 63          cin >> n;
 64          int tmp = (n+eps)*20;
 65          makef(tmp);
 66          int result = f[tmp][6][a[6]];
 67          for (int i=tmp+1; i<=tmp*5; i++)
 68              result = min(result,f[i][6][a[6]]+d[i-tmp][6]);
 69          cout << setw(3) << result << endl;
 70      }
 71      return 0;
 72  }
 73  
 74  void maked() {
 75      for (int i=0; i<=maxn; i++)
 76          for (int j=0; j<=6; j++) d[i][j] = 251;
 77      for (int j=0; j<=6; j++) d[0][j] = 0;
 78      for (int i=1; i<=maxn; i++)
 79          for (int j=1; j<=6; j++)
 80          {
 81              if (coins[j]<=i) d[i][j] = min(d[i-coins[j]][j]+1,d[i][j-1]);
 82              else d[i][j] = d[i][j-1];
 83          }
 84  }
 85  
 86  void makef(int n) {
 87      for (int i=0; i<=n*5; i++)
 88          for (int j=0; j<=6; j++)
 89              for (int k=0; k<=251; k++) f[i][j][k] = 251;
 90      for (int j=0; j<=6; j++)
 91          for (int k=0; k<=251; k++) f[0][j][k] = 0;
 92      for (int i=1; i<=n*5; i++)
 93          for (int j=1; j<=6; j++)
 94          {
 95              f[i][j][0] = f[i][j-1][a[j-1]];
 96              for (int k=1; k<=a[j]; k++)
 97              {
 98                  if (k==1) f[i][j][k] = f[i][j-1][a[j-1]];
 99                  else f[i][j][k] = f[i][j][k-1];
100                  if (coins[j]<=i)
101                  {
102                      if (k>1) f[i][j][k] = min(f[i][j][k],f[i-coins[j]][j][k-1]+1);
103                      else f[i][j][k] = min(f[i][j][k],f[i-coins[j]][j-1][a[j-1]]+1);
104                  }
105              }
106          }
107  }