算法设计与分析 课件 第五章 贪心法 5.1.1 部分背包问题

计算机算法设计与分析第5章贪心法5.1.1部分背包问题给定编号1~n的n个物品，编号i的物品重量wi，价值vi，现用1个负重W的背包来装这些物品，在不超过背包负重的前提下，使得背包装入的总价值最大。与0-1背包问题的区别是这些物品可以分割后部分装入背包，分割后的物品重量价值比不变。5.1.1部分背包问题一个背包负重W=150的7个物品的部分背包问题：物品编号1234567重量wi35306050401025价值vi10403050354030贪心策略1：价值最大策略选择价值最大的物品，可以尽可能快地增加背包的总价值。但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证装入背包的物品总价值达到最大。按照物品价值从大到小排序，价值相同的重量小的优先，可选择4号物品、6号物品，2号物品、5号物品、7号物品（部分装入）。得到背包的总重量为50+10+30+40+20=150，总价值为50+40+40+35+20/25*30=189。物品编号1234567重量wi35306050401025价值vi10403050354030贪心策略2：重量最轻策略选择重量最轻的物品，可以装入尽可能多的物品，从而增加背包的总价值。但背包的价值却不能保证迅速增长，也不一定能保证装入背包的物品总价值达到最大。按照物品重量从小到大排序，可选择6号物品、7号物品、2号物品、1号物品、5号物品和4号物品（部分装入），得到背包的总重量为10+25+30+35+40+10=150，总价值为40+30+40+10+35+10/50*50=165。物品编号1234567重量wi35306050401025价值vi10403050354030贪心策略3：单位重量价值最大策略选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。将物品按照单位重量价格从大到小排序，可选择6号物品、2号物品、7号物品、4号物品和5号物品（部分装入），得到背包总重量为10+30+25+50+35=150，总价值为40+40+30+50+35/40*35=190.625。物品编号1234567重量wi35306050401025价值vi10403050354030结论显然，以上三种贪心策略中，每次选取单位重量价值最大策略使得装入背包的物品总价值最大。背包问题数学模型设xi表示编号为i的物品装入背包情况，0≤xi≤1。根据问题的要求，有如下目标函数和约束条件：证明贪心策略3正确性首先按照每个物品的单位重量价值vi/wi给物品重新排序，排序后的物品也重新编号为1~n，即i<j时有

。贪心策略：从单位重量价值最大的物品开始选择，若将这个物品全部装入背包后，背包没有超过其负重W，则继续选择下一个物品进行装入，当选择某物品装入背包后超过背包负重，则该物品采用部分装入方式将背包装满。证明贪心策略3正确性（1）存在包含单位价值最大物品的最优解。使用反证法来证明第一步选择，因为物品已经按单位重量价值递减排序且w1<W，则部分背包问题存在最优解v1x1+v2x2+...+vnxn。若x1=1，显然最优解包含单位重量价值最大的物品的结论成立。若x1<1，则将背包中重量等于(1-x1)w1的部分物品与物品1交换，这样背包的负重不变，但因，重样重量的物品1具有更大的价值，即等量交换后背包的总价值增加了，这与假设是最优解矛盾。如果w1≥W，则直接装入W重的第1个物品部分即为最优解，总价值为最优解包含单位重量价值最大的物品的结论成立!也即，贪心选择的第一步选择总是会包含在某个最优解中。（2）在完成第一步选择之后，子问题P'()与原问题P()还是同一类问题，意味着我们的选择没有改变问题的结构。令π'为子问题P'的最优解，π为原问题P的最优解，则π=π'+v1。证明贪心策略3正确性证明贪心策略3正确性还是使用反证法来证明这个结论，假设π不是原问题的最优解，原问题P的最优解为π*。根据第一步结论，我们知道最优解π*中一定含有v1，那么π*-v1就应该是子问题P'的解，π*-v1>π-v1=π'，这与π'为子问题P'的最优解定义矛盾。所以π=π'+v1不可能不是最优解，因此原问题的最优解等于子问题最优解加上第一个选择的物