C++ 贪心算法

zltzlt

贪心算法

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

贪心算法举例

（钱币支付问题）假设 1 元、5 元、10 元、20 元、50 元、100 元的纸币分别有 c0、c1、c2、c3、c4、c5 张。

现在要用这些钱来支付 k 元，至少要用多少张纸币？

输入一行：k c0 c1 c2 c3 c4 c5
输出一行：为至少需要纸币的张数。如果找不出钱来，输出 NO。

自己的笨方法：

1. // 钱币支付问题
   
2. 
   
3. #include <iostream>
   
4. using namespace std;
   
5. 
   
6. int main()
   
7. {
   
8.     int c0, c1, c2, c3, c4, c5, k, m = 0;
   
9.     cin >> k >> c0 >> c1 >> c2 >> c3 >> c4 >> c5;
   
10.     while (k)
    
11.     {
    
12.         if (c5 && k > 99)
    
13.         {
    
14.             k -= 100;
    
15.             c5--;
    
16.             m++;
    
17.             continue;
    
18.         }
    
19.         if (c4 && k > 49)
    
20.         {
    
21.             k -= 50;
    
22.             c4--;
    
23.             m++;
    
24.             continue;
    
25.         }
    
26.         if (c3 && k > 19)
    
27.         {
    
28.             k -= 20;
    
29.             c3--;
    
30.             m++;
    
31.             continue;
    
32.         }
    
33.         if (c2 && k > 9)
    
34.         {
    
35.             k -= 10;
    
36.             c2--;
    
37.             m++;
    
38.             continue;
    
39.         }
    
40.         if (c1 && k > 4)
    
41.         {
    
42.             k -= 5;
    
43.             c1--;
    
44.             m++;
    
45.             continue;
    
46.         }
    
47.         if (c0 && k)
    
48.         {
    
49.             k--;
    
50.             c0--;
    
51.             m++;
    
52.             continue;
    
53.         }
    
54.         if (!c0 && k)
    
55.         {
    
56.             cout << "NO";
    
57.             return 0;
    
58.         }
    
59.     }
    
60.     cout << m;
    
61.     return 0;
    
62. }

复制代码

贪心算法总结

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

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

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