实例分析(例31) W3<W2 < W1 ∴首先将物品3放入背包,此时x3=1,背包容量减少W3=10个单 位,还剩余空间ΔM=10。同时,背包获得p3=15的效益增量。 其次考虑物品2。就ΔM=10而言有,也只能选择物品2的一部分 装入背包。下一步将放入物品2的10/15装包,即 2=10/15=2/3 最后,背包装满△M=0,物品1将不能装入背包,故X1=0。 背包最终可以获得效益值=X1p1+x2p2+x3p3 31(次优解,非问题的最优解) 存在的问题:效益值没有得到“最大程度”的增加
实例分析（例3.1) ∵ w3＜w2 ＜w1 ∴ 首先将物品3放入背包，此时x3＝1，背包容量减少w3＝10个单 位，还剩余空间ΔM=10。同时，背包获得p3＝15的效益增量。 其次考虑物品2。就ΔM=10而言有，也只能选择物品2的一部分 装入背包。下一步将放入物品2的10/15装包，即 x2＝10/15＝2/3 最后，背包装满ΔM=0，物品1将不能装入背包，故 x1＝0 。 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 31 (次优解,非问题的最优解) 存在的问题：效益值没有得到“最大程度”的增加
3)最优的度量标准 影响背包效益值得因素: 背包的容量M 放入背包中的物品的重量及其可能带来的效益值 可能的策略是:在背包效益值的增长速率和背包容量消耗速率之间 取得平衡,即每次装入的物品应使它所占用的每一单位容量能获得当 最大的单位效益 在这种策略下的量度是:已装入的物品的累计效益值与所用容量之 比 故,新的量度标准是:每次装入要使累计效益值与所用容量的比值 有最多的增加(首次装入)和最小的减小(其后的装入) 此时,将按照物品的单位效益值:p^w比值的非增次序考虑
3）最优的度量标准 影响背包效益值得因素： ◼ 背包的容量M ◼ 放入背包中的物品的重量及其可能带来的效益值 可能的策略是：在背包效益值的增长速率和背包容量消耗速率之间 取得平衡，即每次装入的物品应使它所占用的每一单位容量能获得当前 最大的单位效益。 在这种策略下的量度是：已装入的物品的累计效益值与所用容量之 比。 故，新的量度标准是：每次装入要使累计效益值与所用容量的比值 有最多的增加（首次装入）和最小的减小（其后的装入）。 此时，将按照物品的单位效益值：pi /wi 比值的非增次序考虑
实例分析(例31) p1/W1<p3/W3<p2W2 首先,将物品2放入背包,此时x2=1,背包容量减少W2=15 个单位,还剩余空间△M=5。同时,背包获得p2=24的 效益增量。 其次,在剩下的物品1和3中,应选择物品3,且就△M=5而言有, 只能放入物品3的一部分到背包中。即 3=5/10=1/2 最后,背包装满△M=0,物品1将不能装入背包,故X1=0。 最终可以获得的背包效益值=X1p1+X2p2+X3p3 =315(最优解)
实例分析（例3.1) ∵ p1/w1＜p3/w3 ＜p2/w2 ∴ 首先，将物品2放入背包，此时x2＝1，背包容量减少w2＝15 个单位，还剩余空间ΔM=5。同时，背包获得p2＝24的 效益增量。 其次，在剩下的物品1和3中，应选择物品3,且就ΔM=5而言有， 只能放入物品3的一部分到背包中 。即 x3＝5/10＝1/2 最后，背包装满ΔM=0，物品1将不能装入背包，故x1＝0 。 最终可以获得的背包效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 31.5 (最优解)
3.背包问题的贪心求解算法 算法3.2背包问题的贪心算法 procedure GREEDY-KNAPSACK(P,W,M, x, n) P(1:n)和W(1:n)分别含有按P(/()≥P(+1)W(+1)排序的n 件物品的效益值和重量。M是背包的容量大小,而X(1:n)是解 向量∥ real P(1: n),W(1 n), X(1: n),M,cu integer I, n Ⅹ←0∥将解向量初始化为O∥ cu←M∥/u是背包的剩余容量∥ for i<1 to n do fw(①> cu then exit endif () cu←Cu-WV( repeat if isn then x(①)←CuW()endf end greeDY-KNAPSACK
3. 背包问题的贪心求解算法 算法3.2 背包问题的贪心算法 procedure GREEDY－KNAPSACK(P,W,M,X,n) //P(1:n)和W(1:n)分别含有按P(i)/W(i)≥P(i＋1)/W(i＋1)排序的n 件物品的效益值和重量。M是背包的容量大小，而X(1:n)是解 向量// real P(1:n), W(1:n), X(1:n), M, cu; integer I,n X←0 //将解向量初始化为0// cu←M //cu是背包的剩余容量// for i←1 to n do if W(i) > cu then exit endif X(i) ←1 cu ←cu-W(i) repeat if i≤n then X(i) ←cu/W(i) endif end GREEDY-KNAPSACK
4.最优解的证明 即证明:由第三种策略所得到的贪心解是问题的最优解 最优解的含义:在满足约束条件的情况下,使目标函数取极(大或 小)值的可行解。 贪心解是可行解,故只需证明:贪心解可使目标函数取得极值
4. 最优解的证明 即证明：由第三种策略所得到的贪心解是问题的最优解。 最优解的含义：在满足约束条件的情况下，使目标函数取极（大或 小）值的可行解。 贪心解是可行解，故只需证明：贪心解可使目标函数取得极值