贪心算法基本思想：在对问题求解时，总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑，算法得到的是某种意义上的局部最优解。

注意：贪心算法的每一步都是最优的解决方案，但整个算法并不一定是最优的（局部最优解）。

贪心算法的经典应用

部分背包问题

背包问题：在限定条件下，如何从众多物品中选出收益最高的几件物品。

背包问题可细分为以下四种：

  • 0-1 背包问题：每件物品都不可再分，要么整个装入背包，要么放弃，不允许出现类似“将物品的 1/3 装入背包”的情况；
  • 部分背包问题：每件物品是可再分的，即允许将某件物品的一部分（例如 1/3）放入背包；
  • 完全背包问题：挑选物品时，每件物品可以选择多个，也就是说不限物品的数量。
  • 多重背包问题：每件物品的数量是有严格规定的，比如物品 A 有 2 件，物品 B 有 3 件。

不同背包问题，对应的解决方案也不用，贪心算法主要解决的就是部分背包问题。

部分背包问题

假设商店中有三种商品，它们各自的重量和收益：

  • 商品 1：重量10斤，收益60元；
  • 商品 2：重量20斤，收益100元；
  • 商品 3：重量30斤，收益120元；

部分背包问题，对于每一件商品，顾客可以只购买其一部分（可再分）。现

现在你有一个最多装50斤商品的背包，你如何购买商品才能使背包中的商品收益达到最大化？

贪心算法思路，计算每个商品的收益率（收益/重量）每次优先选择收益率最大的商品，直到所选商品的总重量达到了50斤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
internal class Program
{
    private static int N = 3;

    // w存储各个商品的重量，p存储各个商品的收益，W表示背包的承重，v是收益率
    private static void Sort(float[] w, float[] p)
    {
        float temp;
        // 使用一个数组按升序来存放每件商品的收益率
        float[] v = new float[N];
        for (int i = 0; i < N; i++)
        {
            // 计算收益率（收益/重量）
            v[i] = p[i] / w[i];
        }
        // 根据收益率升序排序
        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                if (v[i] < v[j])
                {
                    temp = v[i];
                    v[i] = v[j];
                    v[j] = temp;

                    temp = w[i];
                    w[i] = w[j];
                    w[j] = temp;

                    temp = p[i];
                    p[i] = p[j];
                    p[j] = temp;
                }
            }
        }
    }

    /*
     * 贪心算法解决部分背包问题
     * w：记录各个商品的总重量
     * p：记录各个商品的总价值
     * result：记录各个商品装入背包的比例
     * W：背包的容量
    */

    private static void fractional_knaspack(float[] w, float[] p,
        float[] result, float W)
    {
        float temp = 0;
        int i = 0;
        // 根据收益率排序
        Sort(w, p);
        while (W > 0)
        {
            // 从排好序的数组中判断选中物品是否可以整个装进背包
            temp = W > w[i] ? w[i] : W;
            // 不可以，则计算出背包容量还能装下多少
            result[i] = temp / w[i];
            // 背包减去装进物品的重量
            W -= temp;
            i++;
        }
    }

    private static void Main(string[] args)
    {
        // 背包总收益
        float values = 0;
        // 每个商品的重量
        float[] w = { 10, 30, 20 };
        // 每个商品的价值
        float[] p = { 60, 100, 120 };
        float[] result = { 0, 0, 0 };
        // 背包容量
        float W = 50;
        fractional_knaspack(w, p, result, W);
        for (int i = 0; i < w.Length; i++)
        {
            // 放入比例为1，则为整个商品装入背包
            if (result[i] == 1)
            {
                Console.WriteLine("总重量为{0}，总价值为{1}的商品全部装入背包。", w[i], p[i]);
                values += p[i];
            }
            // 放入比例为0，则不装入背包
            else if (result[i] == 0)
            {
                Console.WriteLine("总重量为{0}，总价值为{1}的商品不装入背包。", w[i], p[i]);
            }
            // 某个商品放入多少比例进背包
            else
            {
                Console.WriteLine("总重量为{0}，总价值为{1}的商品装入{2}%背包。",
                    w[i], p[i], result[i] * 100);
                values += p[i] * result[i];
            }
        }
        Console.WriteLine("最终收获的商品价值为{0:N6}。", values);
    }
}

输出结果：

总重量为10，总价值为60的商品全部装入背包。
总重量为20，总价值为120的商品全部装入背包。
总重量为30，总价值为100的商品装入66.66667%背包。
最终收获的商品价值为246.666672。