算法设计与分析 SCAU8595 钱币组合的问题（优先做）

8595 钱币组合的问题（优先做）

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

设有n种不同的钱币各若干，可用这n种钱币产生许多不同的面值。
如给定面值7分，有1分3张，2分3张，5分1张，能组成给定面值7分的方法有如下4种：
3个1分+2个2分； 5个；
1个1分+3个2分； 4个；
2个1分+1个5分； 3个；
1个2分+1个5分； 2个。

上面4种方案的最少张数为2个。

你的编程任务：给定面值m，和n种不同面值钱币及其张数，
（1） 求给定面值m能有多少种不同的构成方法数。
（2） 求给定面值m最少要多少张。

输入格式

第1行有1个正整数n(1<=n<=50)，表示有n种不同的钱币。
第2行有n个数，分别表示每种钱币的面值v[1]…vn。
第3行有n个数，分别表示每种钱币的张数k[1]…kn。
第4行有1个数，表示给定的面值m (1<=m<=20000)。

输出格式

两行：
第一行：计算出给定面值的不同的方法种数。若无法给出找钱方案，返回0数值。
第二行：计算出给定面值所需的最少张数。若无法给出找钱方案，返回“no possible”(无大写，无标点)。

输入样例

3
1 2 5
3 3 1
7

输出样例

4
2

解题思路

给定一个数值sum，假设我们有 m 种不同类型的硬币{ V1, V2, …, Vm}，如果要组合成sum，那么我们有

sum = x1 * V1 + x2 * V2 + … + xm * Vm

求所有可能的组合数，就是求满足前面等值的系数 {x1, x2, …, xm} 的所有可能个数。

从上面的分析中我们也可以这么考虑，我们希望用 n 种硬币构成总面值 sum，根据最后一个钱币 Vm 的系数的取值为无非有这么几种情况，分别取｛0, 1, 2, …, sum / Vm｝，换句话说，上面分析中的等式和下面的几个等式的联合是等价的。

sum = x1 * V1 + x2 * V2 + … + 0 * Vm
sum = x1 * V1 + x2 * V2 + … + 1 * Vm
sum = x1 * V1 + x2 * V2 + … + 2 * Vm
…
sum = x1 * V1 + x2 * V2 + … + k * Vm
其中 k 是该 num 能取的最大数值 K = sum / Vm。（例如：当前总面值为10，最多只能容纳 2张面值为5的纸币，即 2 = 10 / 5）

可是这又有什么用呢？不要急，我们先进行如下变量的定义：

dp[i][sum] = 用前 i 种硬币构成面值为 sum 的所有方案数。

那么题目的问题实际上就是求 dp[n][sum]，即用前 n 种硬币（所有硬币）构成 sum 的方案数。

在上面的联合等式中：

• 当 num = 0 时，有多少种组合呢？ 实际上就是在前 i - 1 种硬币组合成面值 （sum - 0）的前提下，加入0张第 i 种纸币的方案数，即 dp[i - 1][sum - 0] 种
• 当 num = 1 时，有多少种组合呢？ 实际上就是在前 i - 1 种硬币组合成面值 （sum - Vm）的前提下，加入1张第 i 种纸币的方案数，即 dp[i - 1][sum - 1 * Vm] 种
• 当 num = 2 时，有多少种组合呢？ 实际上就是在前 i - 1 种硬币组合成面值 （sum - 2 * Vm）的前提下，加入2张第 i 种纸币的方案数，即 dp[i - 1][sum - 2 * Vm] 种！
• 当加入的第 i 种纸币数到达最多，即 K = sum / Vm 时，所有的这些情况加起来就是我们的dp[i][sum]。

所以：

dp[i][sum] = dp[i-1][sum - 0Vm] + dp[i-1][sum - 1Vm] + dp[i-1][sum - 2Vm] + … + dp[i-1][sum - KVm];
其中K = sum / Vm
相关状态转移方程为：dp[i][sum] += dp[i - 1][sum - num * v[i]];

那么初始情况是什么呢？如果 sum = 0，那么无论有前多少种来组合出面值为0，只有一种可能，就是各个系数都等于0；

即 dp[i][0] = 1 // i = 0, 1, 2, … , m

如果我们用二位数组表示 dp[i][sum], 我们发现第 i 行的值全部依赖与 i - 1 行的值，所以我们可以逐行求解该数组。如果前0种硬币要组成 sum，我们规定为 dp[0][sum] = 0.

因此解题过程如下：

1. dp 方程定义

dp[i][sum] 记录到第 i 种纸币时，面值为 sum 的方案数

2. 状态转移方程

1. 转移方程的初值：dp[0][i] = 0：不用任何币种组成任意钱数，没有这种操作；dp[i][0] = 1; 对于前 i 种纸币，总面值为0的方法只有1种，就是各个系数都等于0。
2. 转移方程的过程：dp[i][sum] += dp[i - 1][sum - num * v[i]]：加上前 i 种纸币面值为 sum - num * v[i] 时的个数，由于 num 是会慢慢变大，即组合能容纳多张第 i 张纸币，因为可能会重复，所以是加上。
3. 转移方程的最终结果：dp[n, m]：合并到第 n 种纸币且总面值为 m 时，总方案数的个数
   
   

3. 算法解题思路

1. 转移方程初始化：dp[0][i] = 0：不用任何币种组成任意钱数，没有这种操作；dp[i][0] = 1; 对于前 i 种纸币，总面值为0的方法只有1种，就是各个系数都等于0。
2. 三层 for 循环，外层 i 控制加入第 i 种纸币到组合，第二层 sum 控制此时组合的面值是多少，最内层 num 控制在组合成 sum 面值的前提下，加入的第 i 种纸币有多少张了，num 的边界条件不仅要满足 num <= sum / v[i]，还要满足 num <= k[i]，即在面值上要小于等于所能容纳的最大张数，即组合面值为10时只能容纳2张面值5的，在数量上要小于等于题目所给出的该张纸币的张数
3. 最终结果：dp[n, m]：合并到第 n 种纸币且总面值为 m 时，总方案数的个数

    // 第i种纸币
    for(i = 1; i <= n; i++) {
        // 面值为 sum 时
        for(sum = 1; sum <= m; sum++) {
            // 该种纸币出几张，不仅要少过该种纸币的张数，还要少过该种纸币允许的最大张数，比如如果10元，最多只能容纳2张5元纸币
            for(num = 0; num <= sum/v[i] && num <= k[i]; num++) {
                dp[i][sum] += dp[i - 1][sum - num * v[i]];
            }
        }
    }
1
2
3
4
5
6
7
8
9
10

当然，此题除了要我们求总方案数，还要求构成面值 m 时的最小张数

4. 求最小张数的解题思路

也用一个状态转移方程来记录 paper[i][sum]： 记录到第 i 种纸币时，面值为 sum 的纸币最小张数

在求 dp 的同时，还要求 paper，具体思路是：

1. 如果此时 dp[i][sum] != 0，即当有方案数，才计算纸币数，否则还是保持0
2. 由于是计算最小纸币数，所以每次要 min，比如说面值为3时，我的纸币数可以是3张1块，或1张2块、1张1块，肯定是取后者。但当纸币数为0时，如果取 min 就会永远为0，所以分开两种情况
3. 当 paper[i][sum] == 0 时，paper[i][sum] = paper[i - 1][sum - num * v[i]] + num：即第 i - 1 种纸币组合成面值为 sum - num * v[i] 时的纸币数前提下加上第 i 种纸币的张数 num
4. 当 paper[i][sum] != 0 时，比较是当前 paper[i][sum] 小，还是第三步要加入的小，即 paper[i][sum] = min(paper[i][sum], paper[i - 1][sum - num * v[i]] + num);

// 当有方案数，才计算纸币数，否则还是保持0
if(dp[i][sum] != 0) {
  // 由于是计算最小纸币数，所以每次要 min 函数，但当纸币数为0时，如果取 min 就会永远为0，所以分开两种情况
  if(paper[i][sum] == 0) {
    paper[i][sum] = paper[i - 1][sum - num * v[i]] + num;
  } else {
    paper[i][sum] = min(paper[i][sum], paper[i - 1][sum - num * v[i]] + num);
  }

}
1
2
3
4
5
6
7
8
9
10

更多注释可查看下方的完整代码中，有助于理解。

可将代码中 cout 相关的注释去掉，通过打印出来的过程来帮助理解。

代码如下

#include 

using namespace std;

int n;
int v[51]; // 每种纸币面值
int k[51]; // 每种纸币张数
int m; // 总面值
int dp[51][20001] = { 0 }; // dp[i][sum] 记录到第 i 种纸币时，面值为 sum 的方案数
int paper[51][20001] = { 0 }; // paper[i][j] 记录到第 i 种纸币时，面值为 j 的纸币张数

/*
3
1 2 5
3 3 1
7
*/

int main()
{
    int i, sum, num;
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> v[i];
    }
    for(i = 1; i <= n; i++) {
        cin >> k[i];
    }
    cin >> m;

    for(i = 0; i <= n; i++) {
        dp[0][i] = 0; // 初始化，不用任何币种组成任意钱数，没有这种操作
    }

    for(i = 0; i <= n; i++) {
        dp[i][0] = 1; // 初始化，每种纸币，总面值为0的方法只有1种
    }


    // 第i种纸币
    for(i = 1; i <= n; i++) {
        // 面值为 sum 时
        for(sum = 1; sum <= m; sum++) {
            // 该种纸币出几张，不仅要少过该种纸币的张数，还要少过该种纸币允许的最大张数，比如如果10元，最多只能容纳2张5元纸币
            for(num = 0; num <= sum/v[i] && num <= k[i]; num++) {
                dp[i][sum] += dp[i - 1][sum - num * v[i]];
                // 当有方案数，才计算纸币数，否则还是保持0
                if(dp[i][sum] != 0) {
                    // 由于是计算最小纸币数，所以每次要 min 函数，但当纸币数为0时，如果取 min 就会永远为0，所以分开两种情况
                    if(paper[i][sum] == 0) {
                        paper[i][sum] = paper[i - 1][sum - num * v[i]] + num;
                    } else {
                        paper[i][sum] = min(paper[i][sum], paper[i - 1][sum - num * v[i]] + num);
                    }

                }

                //cout << "mianzhi=" << v[i] << " maxZhangShu=" << k[i] << " num=" << num << " dp[" << i << "][" << sum << "]=" << dp[i][sum] << endl;
                //cout << " paper[" << i << "][" << sum << "]=" << paper[i][sum] << endl;
            }
        }
    }

    cout << dp[n][m] << endl;

    if(paper[n][m] == 0) {
        cout << "no possible" << endl;
    } else {
        cout << paper[n][m] << endl;
    }


    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

最后

对我感兴趣的小伙伴可查看以下链接

• 我的掘金主页：https://juejin.cn/user/1302297507801358
• 博客主页：http://blog.zhangjiancong.top/
• 公众号：Smooth前端成长记录