最新贪心算法.ppt

第4章 贪心算法
1
第4章 贪心算法
顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。 贪心算法的根本要素

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来到达。这是贪心算法可行的第一个根本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法那么通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
12
贪心算法的根本要素

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
13
贪心算法的根本要素

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差异。
14
贪心算法的根本要素
0-1背包问题：
给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包屡次，也不能只装入局部的物品i。
15
贪心算法的根本要素
背包问题：
与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一局部，而不一定要全部装入背包，1≤i≤n。
这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。
16
贪心算法的根本要素
用贪心算法解背包问题的根本步骤：
首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。假设将这种物品全部装入背包后，背包内的物品总重量未超过C，那么选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
具体算法可描述如下页：
17
贪心算法的根本要素
public static float knapsack(float c,float [] w, float [] v,float [] x)
{
int n=;
Element [] d = new Element [n];
for (int i = 0; i < n; i++) d[i] = new Element(w[i],v[i],i);
(d);
int i;
float opt=0;
for (i=0;i<n;i++) x[i]=0;
for (i=0;i<n;i++) {
if (d[i].w>c) break;
x[d[i].i]=1;
opt+=d[i].v;
c-=d[i].w;
}
if (i<n){
x[d[i].i]=c/d[i].w;
opt+=x[d[i].i]*d[i].v;
}
return opt;
}
算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为
O〔nlogn〕。当然，为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。
18
贪心算法的根本要素
对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，局部闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的