算法设计与分析 第七八九讲.ppt

* 4.2 贪心算法的基本要素 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下： 用贪心算法解背包问题的基本步骤： * 4.2 贪心算法的基本要素 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); int i; for (i=1;i=n;i++) x[i]=0; float c=M; for (i=1;i=n;i++) { if (w[i]c) break; x[i]=1; c-=w[i]; } if (i=n) x[i]=c/w[i]; } 算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为 O（nlogn）。 为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。 * 4.2 贪心算法的基本要素 对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。 * 4.3 最优装载 有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 1、算法描述 最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。 * 4.3 最优装载 templateclass Type void Loading(int x[], Type w[], Type c, int n) { int *t = new int [n+1]; Sort(w, t, n); for (int i = 1; i = n; i++) x[i] = 0; for (int i = 1; i = n w[t[i]] = c; i++) {x[t[i]] = 1; c -= w[t[i]];} } * 4.3 最优装载 2、贪心选择性质 可以证明最优装载问题具有贪心选择性质。 设集装箱按重量从小到大排序，（x1,x2,···,xn）是最优装载问题的一个最优解，又k = min{i | xi = 1}。易知，如果给定的最优装载问题有解，则1≤k≤n。 1） 当 k=1 时，（x1,x2,···,xn）是满足贪心选择性质的一个最优解； 2） 当 k1 时，取y1=1，yk=0，yk=xk，1i≤n，i≠k，则： 因此，（y1，y2，···，yn）是给定的最优装载问题的一个可行解。 又 ，则（y1，y2，···，yn）是满足贪心选择性质的一个最优解。 4.3 最优装载 * * 4.3 最优装载 3、最优子结构性质 设（x1，x2，…，xn）是最优装载问题的满足贪心选择性质的最优解，易知，x1＝1，（x2，x3，…，xn）是船载重量为c-w1且集装箱为｛2，3，…，n｝时相应最优装载问题的最优解，最优装载问题具有最优子结构性质。 由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。 算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。 * 4.4 哈夫曼编码 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 1、前缀码 对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。 * 4.4 哈夫曼编码 编码的前缀性质可以使译码方法非常简单。 表示最优