算法引入

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

这道题解起来很简单，有意思的主要是这道题的最后一句话：“尽可能地提高算法效率”。

思路

这道题不是要求最优解，而是要求可行解，所以有很多求最优解的快捷算法不能使用。
基本算法可以用 快乐蛮力法 直接遍历整个幂集，要求尽可能地提高算法效率，就不能遍历完整个解空间，因此利用的 回溯法 来减去不要的分支

提高方法

1 利用题目要求_每种零钞至少一张_ ，通过一定的预先计算减少解空间，比如对10元的张数来说，由于“每个面额的钞票至少一张的设定，因此最多是9张”
2 利用 回溯法 的思想，剪去不要的子树。同时我还利用1元零钱逐渐递增的特点，通过判断加速遍历左子树。

代码

//回溯法
#include<iostream>
using namespace std;//a[0]表示10元，a[1]表示5元,a[2]表示2元,a[3]表示1元
// 计算和函数
int sum(int a[]) {return 10 * a[0] + 5 * a[1] + 2 * a[2] + 1 * a[3];
}void changeMoney() {int a[4] = {0};int k=1;for(a[0]=1;a[0]<=9;a[0]++)for(a[1]=1;a[1]<20;a[1]++)for(a[2]=1;a[2]<=42;a[2]++)for (a[3] = 1; a[3] <= 83; a[3]++){if (sum(a) <= 98) a[3]++;//左孩子加速遍历if (sum(a) == 100) { cout << "第" << k << "种换法为"<<a[0]<<"张10元，"<<a[1]<<"张5元，"<<a[2]<<"张2元，"<<a[3]<<"张1元"<<endl;k++;}else if (sum(a) > 100) break;//右孩子结点剪枝}
}int main()
{changeMoney();return true;}

参考

网上我看到的都是蛮力法，最多在解空间上有删减,大家也可以参考一下：https://blog.csdn.net/BianChengBuQiuRen/article/details/109105335
https://www.tqwba.com/x_d/jishu/322692.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！