从而证明了贪心解是最优解.ppt

作业 16.1-1 16.1-3 10.3 小数背包问题 * * 10.3 小数背包问题 * * 特殊的0-1背包问题： 如果 w1≤w2 ≤ … ≤ wn, v1 ≥ v2 ≥ … ≥ vn, 则 v1/w1 ≥ v2/w2 ≥ … ≥ vn/wn，此时可以用贪心法求最优解。 0-1-Knapsack( v[], w[], n, c ) { //输出x[1…n] for i=1 to n do x[i]=0; value = 0.0; for i=1 to n do { if ( w[i]c ) { x[i] = 1; c-= w[i]; value +=v[i]; } else break; } return value; } 10.4 最优装载 * * 问题的描述: 轮船载重为c，集装箱重量为wi( i = 1, 2, …, n)，在装载体积不受限制的情况下，将尽可能多的集装箱装上船。 形式化定义： 10.4 最优装载 * * 贪心策略：从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪心策略，首先选择最轻的货箱，然后选择次轻的货箱，如此下去直到所有货箱均装上船或者船上不能容纳其他任何一个货箱。 计算实例：假设 n =8, [w1,w2,…, w8] = [100,200, 50, 90, 150, 50, 20, 80], c=400。 利用贪心算法时，所考察货箱的顺序为7, 3, 6, 8, 4, 1, 5, 2。 货箱7, 3, 6, 8, 4, 1的总重量为390个单位且已被装载，剩下的装载能力为10个单位，小于剩下的任何一个货箱。 在这种贪心解决算法中得到[x1,x2,…,x8] = [1,0,1,1,0,1,1,1]，且∑xi = 6 10.4 最优装载 * * 算法描述： ContainerLoading( x[], w[], c, n) { //x[i]=1当且仅当货箱i被装载，对重量按间接寻址方式排序 new t[n+1]; //产生数组t，用于间接寻址 IndirectSort(w, t, n); //此时，w[t[i]] ≤w[t[i+1]], 1 ≤ i n for i = 1 to n do //初始化x x[ i ]=0; for( i=1; i ≤ n w[t[i]] ≤ c; i++ ) { //按重量次序选择物品 x[t[i]] = 1; c = c- w[t[i]]; //c为剩余容量 } delete t[]; } 时间复杂度：O(nlgn) 10.4 最优装载 * * 贪心性质证明： 不失一般性，假设货箱都排好序，即wi≤wi+1 (1 ≤ i ≤ n)。 令x=[x1,…,xn]为用贪心算法获得的解，y=[y1,…,yn]为一个最优解，分若干步可以将y转化为x，转换过程中每一步都产生一个可行的新y，且∑yi（ 1 ≤ i ≤ n ）的值不变（即仍为最优解），从而证明了x为最优解。 10.5 找钱问题 * * 问题定义： 使用2角5分，1角，5分和1分四种面值的硬币时（各种硬币数量不限），设计一个找A分钱的贪心算法，并证明算法能产生一个最优解。设货币种类P={p1,p2,p3,p4}，di和xi分别是pi的货币单位和选择数量，问题的形式描述为： 10.5 找钱问题 * * 10.5 找钱问题 * * 最优子结构性质证明： 10.5 找钱问题 * * 贪心选择性质证明： 10.5 找钱问题 * * 思考： 如果硬币面值改为1分、5分和1角1分，要找给顾客的是1角5分，是否可以用贪心算法？ 10.6 单源最短路径 * * 问题描述: 给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 如：计算顶点1（源）到所有