贪心法基础

大榕树 \ Pascal语言 \ 算法与技巧

贪心法基础

原文链接：http://www.mydrs.org/program/list.asp?id=85
　　贪心法(greedy method)就是...只顾眼前利益，每次都选最好的。
1)解向量
把可行解写成一个N元组的形式，就是解向量。
2)贪心标准
就是眼前“最好”的标准。例如《背包问题》，标准可以是价值，重量或“性价比”
3)贪心算法
对于解向量的每一维，用贪心标准在所有可能值中选择一个加入到解向量中。
4)什么样的问题可以考虑用贪心？
贪心选择性质：选择具有无后效性，即不依赖与以后将要作出的选择。
最优子结构：全局最优包含局部最优。
5)正确性证明的常见方法
反证法是最常见的。通常把一次贪心选择换成另一个值，再把两个可行解加以比较。
一篇英文文章：Greedy Algorithm
下面举个例子：
[题目]删数问题
键盘输入一个高精度的正整数N，去掉其中任意S个数字后使剩下的数最小。
例如：
N=175438, S=4
可以删去7,5,4,8,得到13。
[分析]很容易想到用贪心，但是贪心标准是什么呢？
删S次，每次删的数要使剩下的数尽量小。例如上面的例子，第一次删7,至少比第一次删1,5,4,3,8好！
这样，删数过程是：
175438
15438
1438
138
13
实现很简单，就是从左向右找到第一个i,使n[i]>n[i+1]，如果找到了，就删第i个，否则删最后一位。
这里一次选择的i是2,2,2,3,因此解向量是：(2,2,2,3)

作者：SRbGa
来源：OIBH
时间：2001-07-01

上一篇：回溯的基本框架
下一篇：贪心法矩阵胚理论介绍