5.1 贪心算法基础

贪心算法在大部分的最优化问题中都可以应用，但并非适用于所有情况。这一节中，我们仍然首先向大家介绍贪心算法的基本思路，并利用一个简单的问题（装载问题）为大家展示贪心算法的用法。

5.1.1 贪心算法基本思想

贪心算法是一种十分接近人类日常思维的解题策略，在日常生活中，人们经常会怀着对目标最直观、最高效的思路去解决问题，虽然这种思路未必可以得到最优解，但是它可以为某些问题确定一个可行性范围。在某些范围内，贪心算法是一个最佳选择。

假设一个商店的收银员有面值为25美分、10美分、5美分及1美分的硬币。一个小孩买了价值少于1美元的糖，并将1美元交给收银员。收银员希望找给小孩的硬币数目最少。如果小孩买了34美分的糖果，那么找钱的方法应该是25美分+25美分+10美分+5美分+1美分。因为我们有种直觉，即在找零钱时，应该优先使用面值大的硬币，剩余的金额就越少。每次都使用当前可以使用的硬币中的最大面额，那么最终就可以使得找给小孩的硬币数目最少。

上面的问题就是日常生活中利用的贪心策略。实际上贪心算法的基本思想是把最优化问题的求解看作是一系列选择，每次选择当前状态下的最优选择（局部最优解）。每做一次选择后，所求问题会简化为一个规模更小的子问题，从而通过每一步的最优解逐步达到整体的最优解。

一般情况下，可以使用如下步骤来设计贪心算法：

5.1.2 贪心算法举例——装载问题

下面来详细分析如何利用贪心策略求解一个经典问题——装载问题。

问题描述：有一批集装箱要装上一艘载重量为C的轮船。其中集装箱i的重量为W_i。现在要求设计一种方法可以在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

问题分析：当载重量为定值C时，W_i越小，可装载的集装箱数量n越大，因此可以将问题划分为i个子问题，只要依次选择最小重量集装箱，满足所有备选集装箱总重量小于或等于C。那么可以用数学的形式把这个问题描述为求解公式：

其中：

x_i∈{0,1},1≤i≤n

基于以上分析，可以很容易地写出用贪心算法解决该问题的伪代码，代码如下所示。