C++ 贪心算法
贪心算法贪心算法是指在问题求解时，总是做出在当前看来是最好的选择。
贪心算法举例
（钱币支付问题）假设 1 元、5 元、10 元、20 元、50 元、100 元的纸币分别有 c0、c1、c2、c3、c4、c5 张。
现在要用这些钱来支付 k 元，至少要用多少张纸币？
输入一行：k c0 c1 c2 c3 c4 c5
输出一行：为至少需要纸币的张数。如果找不出钱来，输出 NO。
自己的笨方法：
// 钱币支付问题
#include <iostream>
using namespace std;
int main()
{
int c0, c1, c2, c3, c4, c5, k, m = 0;
cin >> k >> c0 >> c1 >> c2 >> c3 >> c4 >> c5;
while (k)
{
if (c5 && k > 99)
{
k -= 100;
c5--;
m++;
continue;
}
if (c4 && k > 49)
{
k -= 50;
c4--;
m++;
continue;
}
if (c3 && k > 19)
{
k -= 20;
c3--;
m++;
continue;
}
if (c2 && k > 9)
{
k -= 10;
c2--;
m++;
continue;
}
if (c1 && k > 4)
{
k -= 5;
c1--;
m++;
continue;
}
if (c0 && k)
{
k--;
c0--;
m++;
continue;
}
if (!c0 && k)
{
cout << "NO";
return 0;
}
}
cout << m;
return 0;
}
贪心算法总结
贪心算法不从整体上最优上加以考虑，只做出在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
贪心算法不是对所有问题都能得到整体最优解。
页:
[1]