namespace 枚举与枝剪{ /* * 要找8元钱 * 有5元、2元、1元、5角 * 求所有解决方案 */ class Program { static void Main(string[] args) { //初始化，由于其中涉及到浮点运算，所以每位*10 int total = 80;//80角 int _50 = 50; int _20 = 20; int _10 = 10; int _5 = 5; //50角，最少0张 最多80/50 for (int a = 0; a <= total / _50; a++) { for (int b = 0; b <= total /_20; b++) { for (int c = 0; c <= total / _10; c++) { for (int d = 0; d <= total / _5; d++) { if (a * _50 + b * _20 + c * _10 + d * _5 == total) { Console.WriteLine("5元=" + a + ",2元=" + b + ",1元=" + c + ",5角=" + d); } } } } Console.ReadLine(); } } }} 以上算法未用到“枝剪”，如果运算的数字大一些，例如：800元，十几种零钞，这样计算机就吃不消了，大概要运算一年,因为以上考虑了太多没有意义的数据。例如：取了一张5元面值，不可能取足2张2元。“枝剪”就是去除这种过多的考虑，来增加运算效率
以下是用到“枝剪”的算法：
//初始化，由于其中涉及到浮点运算，所以每位*10 int total = 80;//80角 int _50 = 50; int _20 = 20; int _10 = 10; int _5 = 5; //50角，最少0张 最多80/50 for (int a = 0; a <= total / _50; a++) { for (int b = 0; b <= total /_20; b++) { //枝剪二：过滤非法情况，有可能ab取得过大的值，如果这个名额<0，就没有名额给下面分配了 if ((total - a * 50) < 0) { break; } for (int c = 0; c <= total / _10; c++) { //枝剪三 if ((total - (a * _50 + b * _20 + c * _10)) < 0) { break; } //前面的几种零钞，一共用掉了多少名额，剩下算出d int d = total - (a * _50 + b * _20 + c * _10) / _5; //枝剪一：d值根本不用算，因为可以用abc来求出 //for (int d = 0; d <= total / _5; d++) //{ if (a * _50 + b * _20 + c * _10 + d * _5 == total) { Console.WriteLine("5元=" + a + ",2元=" + b + ",1元=" + c + ",5角=" + d); } //} } } Console.ReadLine(); } 虽然更加混乱、难懂；但是运算速度和效率更快了