2.贪心策略求解 度量标准的选择：三种不同的选择 1)以目标函数作为度量标准 即，每装入一件物品，就使背包背包获得最大可能 的效益增量。 该度量标准下的处理规则： ● 按效益值的非增次序将物品一件件地放入到背包； ● 如果正在考虑的物品放不进去，则只取其一部分装满背 包：如果该物品的一部分不满足获得最大效益增量的度量标准， 则在剩下的物品种选择可以获得最大效益增量的其它物品，将它 或其一部分装入背包。 如：若△M=2,背包外还剩两件物品i,j,且有(p=4,w=4) 和(p=3,w=2),则下一步应选择而非放入背包： p/2=2<p1=3
2. 贪心策略求解 度量标准的选择：三种不同的选择 1）以目标函数作为度量标准 即，每装入一件物品，就使背包背包获得最大可能 的效益增量。 该度量标准下的 处理规则： ● 按效益值的非增次序将物品一件件地放入到背包； ● 如果正在考虑的物品放不进去，则只取其一部分装满背 包：如果该物品的一部分不满足获得最大效益增量的度量标准， 则在剩下的物品种选择可以获得最大效益增量的其它物品，将它 或其一部分装入背包。 如：若ΔM=2,背包外还剩两件物品i,j，且有(pi＝ 4，wi＝4) 和(pj＝ 3，wj＝2)，则下一步应选择j而非i放入背包： pi /2 = 2 ＜ pj＝ 3
实例分析（例4.1) p1>p2>p3 '。首先将物品1放入背包，此时x1=1,背包获得p1=25的效益增量， 同时背包容量减少w1=18个单位，剩余空间△M=2。 其次考虑物品2和3。就△M=2而言有，只能选择物品2或3的一部分 装入背包。 物品2：若X2=2/15,则p2X2=16/5=3.2 物品3：若X3=2/10,则p3X3=3 为使背包的效益有最大的增量，应选择物品2的2/15装包，即 X2=2/15 最后，背包装满，△M=0,故物品3将不能装入背包，X3=0。 背包最终可以获得效益值=X1P1十X2P2十X3P3 =28.2(次优解，非问题的最优 解)
实例分析（例4.1) ∵ p1＞p2＞ p3 ∴ 首先将物品1放入背包，此时x1＝1，背包获得p1＝25的效益增量， 同时背包容量减少w1＝18个单位，剩余空间ΔM=2。 其次考虑物品2和3。就ΔM=2而言有，只能选择物品2或3的一部分 装入背包。 物品2： 若 x2＝2/15， 则 p2 x2＝16/5＝3.2 物品3： 若 x3＝2/10， 则 p3 x3＝3 为使背包的效益有最大的增量，应选择物品2的2/15装包，即 x2＝2/15 最后，背包装满， ΔM=0，故物品3将不能装入背包，x3＝0 。 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 28.2 (次优解,非问题的最优 解)
2)以容量作为度量标准 以目标函数作为度量标准所存在的问题：尽管背包 的效益值每次得到了最大的增加，但背包容量也过快地 被消耗掉了，从而不能装入“更多”的物品。 改进：让背包容量尽可能慢地消耗，从而可以尽量 装入“更多”的物品。 即，新的标准是：以容量作为度量标准 该度量标准下的处理规则： 按物品重量的非降次序将物品装入到背包； ●如果正在考虑的物品放不进去，则只取其一部 分装满背包；
2）以容量作为度量标准 以目标函数作为度量标准所存在的问题：尽管背包 的效益值每次得到了最大的增加，但背包容量也过快地 被消耗掉了，从而不能装入“更多”的物品。 改进：让背包容量尽可能慢地消耗，从而可以尽量 装入“更多”的物品。 即，新的标准是：以容量作为度量标准 该度量标准下的处理规则： ● 按物品重量的非降次序将物品装入到背包； ● 如果正在考虑的物品放不进去，则只取其一部 分装满背包；
实例分析（例4.1） ,w3<W2<W1 。首先将物品3放入背包， 此时x3=1,背包容量减少w3=10个 单位，剩余空间△M=10。同时，背包获得p3=15的效益增量。 其次考虑物品1和2。就△M=10而言有，也只能选择物品1或2 的一部分装入背包。为使背包的按照“统一”的规则，下一步 将放入物品2的10/15装包，即 X2=10/15=2/3 最后，背包装满△M=0,故物品1将不能装入背包，x1=0 背包最终可以获得效益值=Xp1十X2P2十X3P3 =31(次优解，非问题的最优解， 存在的问题：效益值没有得到“最大”的增加
实例分析（例4.1) ∵ w3＜w2 ＜w1 ∴ 首先将物品3放入背包，此时x3＝1，背包容量减少w3＝10个 单位，剩余空间ΔM=10。同时，背包获得p3＝15的效益增量。 其次考虑物品1和2。就ΔM=10而言有，也只能选择物品1或2 的一部分装入背包。为使背包的按照“统一”的规则，下一步 将放入物品2的10/15装包，即 x2＝10/15＝2/3 最后，背包装满ΔM=0，故物品1将不能装入背包，x1＝0 。 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 31 (次优解,非问题的最优解) 存在的问题：效益值没有得到“最大”的增加
3)最优的度量标准 影响背包效益值的因素： 必 背包的容量M 放入背包中的物品的重量及其可能带来的效益值 可能的策略是：在背包效益值的增长速率和背包容量消耗速率之 间取得平衡，即每次装入的物品应使它所占用的每一单位容量能获得 当前最大的单位效益。 在这种策略下的量度是：已装入的物品的累计效益值与所用容量 之比。 故，新的量度标准是：每次装入要使累计效益值与所用容量的比 值有最多的增加和最小的减小。 此时，将按照物品的单位效益值：pw比值（密度）的非增次序 考虑
3）最优的度量标准 影响背包效益值的因素： ❖ 背包的容量M ❖ 放入背包中的物品的重量及其可能带来的效益值 可能的策略是：在背包效益值的增长速率和背包容量消耗速率之 间取得平衡，即每次装入的物品应使它所占用的每一单位容量能获得 当前最大的单位效益。 在这种策略下的量度是：已装入的物品的累计效益值与所用容量 之比。 故，新的量度标准是：每次装入要使累计效益值与所用容量的比 值有最多的增加和最小的减小。 此时，将按照物品的单位效益值：pi /wi 比值（密度）的非增次序 考虑