只考虑到多装些物品，但由于单位价值未必高，总价值不能达到最大；按原则b来装，每次选择的价值最大，但同时也可能占用了较大的空间，装的物品少，未必能够达到总价值最大。比较合理的原则是c）。事实上，按照原则c）来装，确实能够达到总价值最大。程序511背包问题贪心算法GreedyK
apsackpwMx
价值数组p1
、重量数组w1
，它们元素的排列顺序满足piwi≥pi1wi1M是背包容量，x是解向量realp1
w1
x1
Mrci
tegeri
x0将解向量初始化为零rcM是背包剩余容量初始化为Mforifrom1to
doifwircthe
exite
difxi1rcrcwie
dforifi≤
the
xircwie
dife
dGreedyK
apsack例子
3M20p252415w181510（说明该算法的执行情况）定理511如果p1w1≥p2w2≥≥p
w
则GreedyK
apsack对于给定的背包问题实例生成一个最优解。证明设xx1x2x
是GreedyK
apsack所生成的解，但不是最优解。因不妨设xj是第一个这样的分量。于是，1≤ij时，xi1；当而必有某个xi不为1。
f3
当ij，0≤xi1；当ji≤
时，xi0。不妨假定∑wixiM。因为x不是最设优解，必存在解向量yy1y2y
使得∑piyi∑pixi。k是使得yk≠xk的最小下标，ykxk这是因为：kj时，k1上述不等式自然成立；k≥j则当x当时，因为x1y1，xk1yk1xk10x
0所以由xkyk可推出
∑wiyi∑wixiM，y不是解向量，矛盾。
i1i1



由ykxk，可以假定∑wiyiM，进而有
i1


ik1
∑wiyi≥wkxkyk。


现在取新的向量zz1z2z
满足
z1y1xk1yk1zkxk，0≤zk1≤yk10≤z
≤y

而且
k1≤i≤

∑wiyiziwkzkyk∑wizi∑wiyiwkzk∑wizi
1≤i≤k1k1≤i≤

由上段的不等式，这样的向量z是存在的，而且是背包问题的可行解，因为
1≤i≤


1≤i≤k11≤i≤

∑wiyi∑wiyi
k≤i≤

∑wiyi≤M
至此，我们找到一个新的解向量z。以下证明它的总价值不小于y的总价值：
1≤i≤

∑pizi∑piyizkykwkpkwk∑yiziwipiwi
1≤i≤
ki≤

≥
1≤i≤

∑piyizkykwk∑yiziwipkwk
k1≤i≤



1≤i≤

∑piyi
中间的不等式是由于当ik时有pkwk≥piwi而得。但是z与x的不同分量的个数比y与x的不同分量的个数至少减少一个。zr