按照原则c来装,确实能够达到总价值最大。 0/1背包问题贪心算法 Greedy Knapsack(p,w,M,x,n)∥价值数组p[n]、重量数组w[1nl, ∥它们元素的排列顺序是p[iwi]≥p[i+1/w[t+1l,M是背包容量, ∥x是解向量 real pll: n, w[l: n), x[l n], M,rc, nteger 1, n, x=0,∥将解向量初始化为零 rc=M;∥/是背包剩余容量初始化为M for i from 1 to n do if wi> rc then exit endif x[1F1; rc=rc-w[i]; endfor if i<n then x[=rc/w[i] endif end greedy Knapsack 定理1如果p[1]/w[2]≥p[2]/w[2]≥……≥p[n/w[n],则 GreedyKnapsack对于给定的0/1背包问题实例生成一个最优解。 证明设x=(x,x2,…,xn)是 Greedy Knapsack所生成的解,但不是 最优解。因而必有某个x不为1。不妨设x是第一个这样的分量。于 是,当1≤ij时,x1=1;当jin时,x1=0;当ij时,0≤x<1按照原则 c 来装，确实能够达到总价值最大。 0/1 背包问题贪心算法 GreedyKnapsack(p, w, M, x, n) //价值数组 p[1:n]、重量数组 w[1:n]， //它们元素的排列顺序是p[i]/w[i]≥p[i+1]/w[i+1]; M是背包容量， // x 是解向量 real p[1:n], w[1:n], x[1:n], M, rc; integer i, n; x=0; // 将解向量初始化为零 rc=M; // 是背包剩余容量初始化为 M for i from 1 to n do if w[i] > rc then exit endif x[i]=1; rc=rc-w[i]; endfor if i≤n then x[i]=rc/w[i]; endif end GreedyKnapsack 定理 1 如 果 p[1]/w[2] ≥ p[2]/w[2] ≥ ⋅⋅⋅⋅⋅⋅ ≥ p[n]/w[n], 则 GreedyKnapsack 对于给定的 0/1 背包问题实例生成一个最优解。 证明 设 x=(x1,x2,⋅⋅⋅⋅⋅⋅,xn)是 GreedyKnapsack 所生成的解，但不是 最优解。因而必有某个 xi不为 1。不妨设 xj是第一个这样的分量。于 是，当 1≤ i<j 时，xi＝1；当 j<i≤n 时，xi＝0；当 i=j 时，0≤xi<1