动态规划（三）——最少硬币问题

一、最少硬币问题

有n种硬币，面值为v1…vn，数量无限，选用硬币，使其和金额为s，要求求出最少的硬币组合。

首先我们应该有打表的思想，将任意金额的最少硬币组合数量存到一个数组里，输入一个金额时就可以直接查询数组中对应的硬币最少数量。

定义一个int Min[MONEY]，Min[i]是金额i对应的最少硬币数量。Min[i]这样记录子问题最优解的数据称为“状态”。

讲解以5种面值（1、5、10、25、50）的硬币为例：

1. 第一步：只使用1分硬币。
   初始值Min[0] = 0，表示0个硬币可以表示0金额，其他的Min[i]为无穷大。
   那Min[1]如何计算？
   这时可以在Min[0]的基础上加一个1分硬币，此时Min[1] = Min[0] + 1 = Min[1] = Min[1-1] +1 。
   此时可以推导出第一个递推公式：
   Min[i] = min(Min[i]，Min[i-1]+1)
   故只用1分硬币的组合结果如下：
   

2. 第二步：在使用1分硬币的基础上增加第二大面值的5分硬币
   此时要在第一步状态的基础上从金额为5开始转换（若金额小于5时，不能用5分硬币替换）
   i = 5时，相当于在i = 0的基础上加一个5分硬币，得到Min[5] = Min[5-5] +1 = 1。
   1分硬币+5分硬币组合的结果如下：
   第一步i=5时，只用1分硬币状态的结果Min[5] = 5，此时根据推导公式
   Min[i] = min(Min[i]，Min[i-5]+1)
   可知，Min[5-5]+1=1比 Min[5]=5更小，故Min[5]=1。

3. 第三步：继续处理其他面值的硬币。
   接下来就是在第二步的基础上将面值为10的硬币转换。
   例如i= 10时，相当于在i = 0的基础上加了一个10分硬币，此时Min[10] = Min[10-10] + 1 = 1。
   又第二步中Min[10] = 2，
   故Min[10] = min(Min[10] ，Min[10-10]+1) = Min[10-10]+1 = 1。
   

   所以找出规律，所有面值的递推公式都是：
   Min[i] = min（Min[i]，Min[i-面值]+1）

代码如下：

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const int money = 200;    //定义最大金额
const int num = 5;        //五个硬币
int type[num] = {1,5,10,25,50};        //五种面值
int Min[money];

void solve() {
  for (int i = 1; i < money; i++)
    Min[i] = INT_MAX;//初始值为无穷大
  Min[0] = 0;
  for (int i = 0; i < 5; i++) {
    for (int j = type[i]; j <= money; j++) {
      Min[j] = min(Min[j], Min[j-type[i]]+1);
    }
  }
}
int main() {
  fio
  solve();
  int s;
  while (cin >> s) {
    cout << Min[s] << endl;
  }
}

二、打印最少硬币组合

若要打印最少硬币的组合方案，就存一个记录金额 i 所需要的最后一种面值的数组Min_Path[]，用这个数组倒推即可得到硬币组合方案。

查询 i 的最优组合：

1. 查询Min_Path[i]，并得到结果k1

2. i-k1=a1,并得到Min_Path[a1] = k2

3. a1-k2 = a2，继续计算Min_Path[a2]。
   重复计算坐标与对应Min_Path[]数组的差值，并计算Min_Path[差值]的结果，直到计算结果为0。

   得出的k1…kj即为结果

如图，计算出Min[]和Min_Path[]：
实例解释，当i=7时：
①Min_Path[7] = 5，说明金额为7的组合中最后一张需要的面值为5。
②Min_Path[7-5]=Min_Path[2] = 1，表示接下来需要的最后一张面值为1。
③Min_Path[2-1]=Min_Path[1]=1，还有一张面值为1。
故i=7时，组合为5分硬币+1分硬币+1分硬币。

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const int money = 200;    //定义最大金额
const int num = 5;        //五个硬币
int type[num] = {1,5,10,25,50};        //五种面值
int Min[money];
int Min_Path[money];
void solve() {
  for (int i = 0; i < money; i++)
    Min[i] = INT_MAX; 
  Min[0] = 0;
  for (int i = 0; i < num; i++) {
    for (int j = type[i]; j < money; j++) {
      if (Min[j] > (Min[j-type[i]]+1)) {
        Min[j] = Min[j-type[i]]+1;
        Min_Path[j] = type[i];
      }
    }
  }
}
void print(int *Min_Path, int s) {
  while (s) {
    printf("%d ", Min_Path[s]);
    s -= Min_Path[s];
  }
}
int main() {
  fio
  int s;
  solve();
  while (cin >> s) {
    cout << Min[s];
    print(Min_Path, s);
  }
}