清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.2贪心算法的基本要素 背包问题: 与0-1背包问题类似,所不同的是在选择物品i入 背包时,可以选择物品喲一部分,而不一定要全部装 入背包,1≤i≤n 这2类问题都具有最优子结构性质,极为相似,但背 包问题可以用贪心算法求解,而0-1背包问题却不能用 贪心算法求解。 16
16 4.2 贪心算法的基本要素 • 背包问题： 与0-1背包问题类似，所不同的是在选择物品i装入 背包时，可以选择物品i的一部分，而不一定要全部装 入背包，1≤i≤n。 这2类问题都具有最优子结构性质，极为相似，但背 包问题可以用贪心算法求解，而0-1背包问题却不能用 贪心算法求解
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.2贪心算法的基本要素 用贪心算法解背包问题的基本步骤: 首先计算每种物品单位重量的价值Vi/wi,然后,依贪心选 择策略,将尽可能多的单位重量价值最高的物品装入背包。 若将这种物品全部装入背包后,背包内的物品总重量未超过 C,则选择单位重量价值次高的物品并尽可能多地装入背包。 依此策略一直地进行下去,直到背包装满为止。 具体算法可描述如下页 17
17 4.2 贪心算法的基本要素 用贪心算法解背包问题的基本步骤： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选 择策略，将尽可能多的单位重量价值最高的物品装入背包。 若将这种物品全部装入背包后，背包内的物品总重量未超过 C，则选择单位重量价值次高的物品并尽可能多地装入背包。 依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页：
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.2贪心算法的基本要素 public static float knapsack(float c, float w, float v, float[x) int nav. length Element d=new Element [n 算法 knapsack的 for(inti=0,i<m计+= new element(响ⅶ主要计算时间在于将 Merge Sort. merge Sort(d) 各种物品依其单位重 n float op t=0 量的价值从大到小排 for(F=0;<n;计+)x[=0, 序。因此,算法的计 for(=0;Kn;计+){ 算时间上界为 if(di]. wc) break x[]1 o( nlogn)。当然, opt+=d[iv 为了证明算法的正确 c一d[w, 性,还必须证明背包 if (K<n)f 问题具有贪心选择性 x[diic/d]. w 质 opt+=x[di]. i]*d return opt, 18
18 4.2 贪心算法的基本要素 • 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 (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）。当然， 为了证明算法的正确 性，还必须证明背包 问题具有贪心选择性 质
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.2贪心算法的基本要素 对于0-1背包问题,贪心选择之所以不能得到最优解是因 为在这种情况下,它无法保证最终能将背包装满,部分闲 置的背包空间使每公斤背包空间的价值降低了。事实上, 在考虑0-1背包问题时,应比较选择该物品和不选择该物 品所导致的最终方案,然后再作出最好选择。由此就导出 许多互相重叠的子问题。这正是该问题可用动态规划算法 求解的另一重要特征。 实际上也是如此,动态规划算法的确可以有效地解0-1 背包问题
19 4.2 贪心算法的基本要素 对于0-1背包问题，贪心选择之所以不能得到最优解是因 为在这种情况下，它无法保证最终能将背包装满，部分闲 置的背包空间使每公斤背包空间的价值降低了。事实上， 在考虑0-1背包问题时，应比较选择该物品和不选择该物 品所导致的最终方案，然后再作出最好选择。由此就导出 许多互相重叠的子问题。这正是该问题可用动态规划算法 求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0-1 背包问题
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.3最优装载 有一批集装箱要装上一艘载重量为c的轮船。其中 集装箱i的重量为Wi。最优装载问题要求确定在装载体 积不受限制的情况下,将尽可能多的集装箱装上轮船。 1.算法描述 最优装载问题可用贪心算法求解。采用重量最轻 者先装的贪心选择策略,可产生最优裝载问题的最优 解。具体算法描述如下页。 20
20 4.3 最优装载 有一批集装箱要装上一艘载重量为c的轮船。其中 集装箱i的重量为Wi。最优装载问题要求确定在装载体 积不受限制的情况下，将尽可能多的集装箱装上轮船。 1.算法描述 最优装载问题可用贪心算法求解。采用重量最轻 者先装的贪心选择策略，可产生最优装载问题的最优 解。具体算法描述如下页