【数据结构与算法】穷举搜索

2024/10/6 12:30:23 来源：https://blog.csdn.net/qq_74047911/article/details/141366807 浏览: 次关键词：【数据结构与算法】穷举搜索

穷举搜索目录

一.穷举搜索的原理
二.穷举问题的引入
三.穷举搜索的实现
四.穷举搜索的高效版

一.穷举搜索的原理

列出所有可能出现的情况,逐个判断有那些是符合问题要求的条件.
通常可以从两方面分析:

问题所涉及的情况
答案需要满足的条件

二.穷举问题的引入

有20枚硬币，可能包括4种类型：1元、5角、1角和5分。
已知20枚硬币的总价值为10元，求各种硬币的数量。
在这里插入图片描述

三.穷举搜索的实现

根据我们两个方面的分析,先将所有的可能列出来.
1元的最多10枚,伍角,一角,五分都最多只有20枚.
因为分角按元来算有小数,不方便,所以我们统一用分来算.

#include <iostream>
using namespace std;int main()
{int a100 = 0;//1元的硬币的数量int a50 = 0;int a10 = 0;int a5 = 0;int cnt = 0;for (a100 = 0; a100 <= 10; a100++){for (a50 = 0; a50 <= 20; a50++){for (a10 = 0; a10 <= 20; a10++){for (a5 = 0; a5 <= 20; a5++){if ((a100 * 100 + a50 * 50 + a10 * 10 + a5 * 5) == 1000 && (a100 + a50 + a10 + a5) == 20){cout << a100 << "," << a50 << "," << a10 << "," << a5 << endl;cnt++;}}}}}cout << "可行的解决方案总共有:" << cnt <<endl;system("pause");return 0;
}

另一方面就是条件,就是总值10元,硬币总个数20.
运行结果:
在这里插入图片描述

四.穷举搜索的高效版

就是减少了不可能出现的情况.

#include <iostream>
using namespace std;int main()
{int a100 = 0;//1元的硬币的数量int a50 = 0;int a10 = 0;int a5 = 0;int cnt = 0;for (a100 = 0; a100 <= 10; a100++){for (a50 = 0; a50 <= (1000-a100*100)/50; a50++){for (a10 = 0; a10 <= (1000 - a100 * 100-a50*50)/10; a10++){for (a5 = 0; a5 <=(1000-a100*100-a50*50-a10*10)/5; a5++){if ((a100 * 100 + a50 * 50 + a10 * 10 + a5 * 5) == 1000 && (a100 + a50 + a10 + a5) == 20){cout << a100 << "," << a50 << "," << a10 << "," << a5 << endl;cnt++;}}}}}cout << "可行的解决方案总共有:" << cnt <<endl;system("pause");return 0;
}

运行结果:
在这里插入图片描述

2024年8月20日19:54:30