C++ 贪心算法

zltzlt

贪心算法

贪心算法是指在问题求解时，总是做出在当前看来是最好的选择。

贪心算法举例

（钱币支付问题）假设 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;
}

贪心算法总结

贪心算法不从整体上最优上加以考虑，只做出在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

贪心算法不是对所有问题都能得到整体最优解。