将一张100 元的钞票换成1 元、2元、5 元和10 元的零钱，每种零钞至少一张

目录

题目

解题思路

代码

---

题目

将一张100 元的钞票换成1 元、2元、5 元和10 元的零钱，每种零钞至少一张，编写程序输出所有的换法，尽可能地提高算法效率。

解题思路

似乎可以使用dfs和dp，但是这题给的样例就这一个，直接模拟也可以，不过为了满足任意的金额进行换算，我还是使用dfs吧。

其中n为输入的金额，这里为100

设置一个a数组存储一下每中面额的数目

然后进行dfs，传入n和index，其中n表示当前剩余的金额

index表示使用了几种面额，用来保证每种面额都至少有一张（满足题目条件）

还有一个问题就是要进行去重的，比如5元，我们可以选2,2,1，也可以选2,1,2，这样2的张数和一的张数都相同，输出时没有什么区别。这时采取的策略就是先枚举10，然后有一张后就枚举5，一直直到1，这样第一个结果就是1张10，一张5，一张2，83张1，然后再增加一张2，减少2张1，依次类推，就能避免重复解。

代码

#include<iostream>
#include<bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int a[N];
//用来记录每个面额的数目int coins[] = {10, 5, 2, 1}; // 面额从大到小排列void dfs(int n,int index) {if(index == 4){if(n == 0){if(a[0] >= 1 && a[1] >= 1 && a[2] >= 1 && a[3] >= 1) {cout << "10元张数：" << a[0] << " 5元张数：" << a[1] << " 2元张数：" << a[2] << " 1元张数：" << a[3] << '\n';return;}}return;}if(n < 0)//如果选的小于0了直接返回return;// 当前面额的最大可能数量int maxCount = n / coins[index];//至少选一张，最多选maxCount张for (int i = 1; i <= maxCount; ++i) {a[index] = i;dfs(n - i * coins[index],index + 1);}
}int main()
{int n;cin >> n;dfs(n,0);return 0;
}