《算法设计与分析》--《贪心算法》--随笔

1、定义:贪心算法其实就是自己通过一系列的选择得到问题的解，取数每次做的选择就是当前状态下局部最好的选择。

尽管这种方式不一定能够获得最优解，但是在许多情况下是能够达到预期的目的的。活动安排问题就是典型的贪心算法。

2、 性质:满足贪心算法求解必须满足贪心选择性质和最优子结构性质。

3、和动态规划的区别: 其实贪心算法就是通过所求问题的整体最优解可以通过一系列的局部最优的选择来达到。动态规划算法中每步做出的选择是依赖于自己子问题的解。只有我们自己把子问题解决了才能够做动态规划的相关操作，所以是自底向上的。

但是贪心算法是仅仅在当前的一个状态下面做出最好的选择，不会去依赖其他的部分，所以贪心算法也是自顶向下的一种算法，迭代的方式做出相应的贪心选择，在作出了选择之后都是将当前问题简化为规模更小的问题！

4、贪心选择的思考： 对于一个具体的问题，要确定其是否具有贪心选择性质，我们就必须去证明每一步做出的贪心选择最终会导致整个问题的整体最优解，做出贪心选择后，原问题才会简化为规模更小的子问题，最终通过每一步的贪心选择，最终得到问题的整体最优解！

5、最优子结构性质: 当一个问题的最优解包含子问题的最优解时，称此问题具有最优子结构性质。

6、两个背包例子： 其实0-1背包问题和背包问题都是具有最优子结构性质的，但是背包问题是可以使用贪心算法求解，0-1背包却是使用动态规划算法求解(背包问题是能够装入物品的一个部分，但是0-1是不能装入部分物品进去)。

7、 背包问题步骤:首先计算每种物品的单位重量的价值Vi/Wi,然后根据贪心选择策略，尽可能装入单位价值最高的物品进入背包。如将该种物品全部装入背包后，包内的物品重量没有超过C，那么选择单位价值次高的物品装入，直到背包装满位置。

具体算法如下：

public static float knapsack(float c,float[] w,float[] v,float[] x){

 int n = v.length;
Element[] d = new Element[n];

for(int i = 0;i<n;i++){
d[i] = new Element(w[i],v[i],i);
MergeSort.mergeSort(d);
int i;
float opt = 0;
for(int i =0;i<n;i++)x[i] = 0;
for(int 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;
}


}

说明：该算法其实最主要在于计算了将单位重量的价值从大到小的排序。对于0-1背包问题，因为贪心选择不能保证最终可以把背包填满，部分闲置的背包空间使每公斤背包的价值降低了。