贪心法(greedy method)是一个把复杂问题分解为一系列较为简单的局部最优选择，每一步选择都是相对于当前解的一个扩展，直到获得问题的完整解。贪心法的典型应用是求解最优化问题，而且对许多问题都能得到整体最优解，即使不能得到整体最优解，通常也是最优解的很好近似。
概述
贪心法的设计思想
贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总是能获得整体最优解(optimal solution)，但通常能获得近似最优解(near-optimal solution)。如果一个问题的最优解只能用蛮力法穷举得到，则贪心法不失为寻找问题近似最优解的一个较好方法。
书中讲到的一个例子很形象，这里摘录下：假设有面值为5元、2元、1元、5角、2角、1角的货币，需要找给顾客4元6角现金，为使付出的货币的数量最少，首先选出1张面值不超过4元6角的最大面值的货币，即2元，再选出一章面值不超过2元6角的最面值的货币，即2元，再选出1张面值不超过6角的最大面值的货币，即6觉，再选出1张面值不超过1角的最大面值的货币，即1角，总共付出4张货币。再付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定。付款问题的贪心酸则是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正是贪心法的设计思想。
上述付款问题应用贪心法得到的是整体最优解，但是如果把面值改为3元、1元、8角、1角，找给顾客的是1个3元、1个1元、1个5角和一个4角共4张货币，但最优解确实3张货币：1个3元和2个8角。对于一个具体的问题，怎么知道是否可以用贪心法求解，以及能否得到问题的最优解呢？这个问题很难给予肯定的回答。但是，从许多可以用贪心法求解的问题中看到，这类问题一般具有两个重要的性质：最优子结构性质（optimal substructure property)和贪心选择性质（greedy selection property)。
（1）最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称次问题具有最优子结构性质，也成此问题满足最优性原理。问题的最优子结构性质是该问题可以用动态规划法或贪心法求解的关键特征。
在分析问题是否具有最优子结构性质时，通常先假设由问题的最优解导出的子问题不是最优的，然后证明在这个假设下可以构造出比原问题的最优解更好的解，从而导致矛盾。
(2)贪心选择性质
所谓贪心选择性质时指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到，这是贪心法和动态规划法的主要区别。在动态规划法中，每步所做出的选择（决策）往往依赖于相关子问题的解，因而只有在求出相关子问题的解后，才能做出选择。而贪心法仅在当前状态下做出最好选择，即局部最优选择，然后再去求解做出这个选择后产生的相应子问题的解。正是由于这种差别，动态规划法通常以自底向上的方式求解各个子问题，而贪心法通常以自顶向下的方式做出一系列的贪心选择，每做一次贪心选择就将问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。通常先考察问题的一个整体最优解，并证明可修改这个最优解，使其从贪心选择开始。做出贪心选择后，原问题简化为规模较小的类似子问题，然后，用数学归纳法证明，通过每一步的贪心选择，最终可得到问题的整体最优解。
贪心法的求解过程
贪心法通常用来求解最优化问题，它犹如登山一样，一步一步向前推进，从某一个初始状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数增长最快（或最慢）为准则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。一般来说，用贪心法求解问题应该考虑如下几个方面：
(1)候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。
(2)解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。
(3)解决函数solution:检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是否已付出的货币金额恰好等于应付款。
(4)选择函数select:即贪心策略，这是贪心法的关键，它指出哪个候选对象最优希望构成问题的解，选择函数通常和目标函数相关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。
(5)可行函数feasible:检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。 例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不应超过应付款。
开始时解集合S为空，然后使用选择函数select按照某种贪心策略，从候选集合C中选择一个元素x，用可行函数feasible取判断解集合S加入x后是否可行，如果可行，把x合并到解集合中，并把它从候选集合C中删去；否则，丢弃x，从候选集合C中根据贪心策略再选择一个元素，重复上述过程，直到找到一个满足解决函数solution的完整解。贪心法的一般过程如下：
Greedy(C) //C是问题的输入集合即候选集合
{
S = {}; //初始解集合为空集
while(not solution(S)）//集合S没有构成问题的一个解
{
x = select(C); //在候选集合C中做贪心选择
if feasible(S, x) //判断集合S中加入x后的解是否可行
S = S+{x};
C = C - {x};
}
return S;
}贪心法是在少量计算的基础上做出贪心选择而不急于考虑以后的情况，这样一步一步扩充解，每一步军事建立在局部最优解的基础上，而每一步又都扩大了部分解。因为每一步所做出的选择仅基于少量的信息，因而贪心发的效率通常很高。贪心法的困难在于证明得到的解确实是问题的整体最优解。