max vi xi
i 1
n
于是，背包问题归结为寻找一个满足约束条 件式，并使目标函数式达到最大的解向量X=(x1, x2, …, xn)。
至少有三种看似合理的贪心策略： （1）选择价值最大的物品，因为这可以尽可能快 地增加背包的总价值。但是，虽然每一步选择获得 了背包价值的极大增长，但背包容量却可能消耗得 太快，使得装入背包的物品个数减少，从而不能保 证目标函数达到最大。 （2）选择重量最轻的物品，因为这可以装入尽可 能多的物品，从而增加背包的总价值。但是，虽然 每一步选择使背包的容量消耗得慢了，但背包的价 值却没能保证迅速增长，从而不能保证目标函数达 到最大。 （3）选择单位重量价值最大的物品，在背包价值 增长和背包容量消耗两者之间寻找平衡。
算法
main( ) { int i,j,n,GZ,A； int B[8]={0,100,50,20,10,5,2,1},S[8]; input(n); for(i=1;i<=n;i++) { input(GZ); for(j=1,j<=7;j++) { A=GZ/B[j]; S[j]=S[j]+A; GZ=GZ-A*B[j];} } for(i=1;i<=7;i++) print(B[i], “----”, S[i]); }
∞ b 4 0 a 8 h ∞ 4 b 4 0 a 8 h 8 11 7 11 7
8 ∞ i 6 1 2
∞ c
7
∞ d 14 9 e ∞ 10
4 g ∞
2
f ∞
(a)
8 ∞ i 6 1 g ∞ 2 4 f ∞ ∞ c 7 ∞ d 14 9 e ∞ 10 2
贪心法求解活动安排问题的关键是如何选择贪心策略，使 得按照一定的顺序选择相容活动，并能安排尽量多的活动。至 少有两种看似合理的贪心策略： （1）最早开始时间：这样可以增大资源的利用率。 （2）最早结束时间：这样可以使下一个活动尽早开始。
