算法設(shè)計(jì)與分析 課件 第五章 貪心法 5.1.1 部分背包問題

計(jì)算機(jī)算法設(shè)計(jì)與分析第5章貪心法5.1.1部分背包問題給定編號(hào)1~n的n個(gè)物品，編號(hào)i的物品重量wi，價(jià)值vi，現(xiàn)用1個(gè)負(fù)重W的背包來裝這些物品，在不超過背包負(fù)重的前提下，使得背包裝入的總價(jià)值最大。與0-1背包問題的區(qū)別是這些物品可以分割后部分裝入背包，分割后的物品重量?jī)r(jià)值比不變。5.1.1部分背包問題一個(gè)背包負(fù)重W=150的7個(gè)物品的部分背包問題：物品編號(hào)1234567重量wi35306050401025價(jià)值vi10403050354030貪心策略1：價(jià)值最大策略選擇價(jià)值最大的物品，可以盡可能快地增加背包的總價(jià)值。但背包容量卻可能消耗得太快，使得裝入背包的物品個(gè)數(shù)減少，從而不能保證裝入背包的物品總價(jià)值達(dá)到最大。按照物品價(jià)值從大到小排序，價(jià)值相同的重量小的優(yōu)先，可選擇4號(hào)物品、6號(hào)物品，2號(hào)物品、5號(hào)物品、7號(hào)物品（部分裝入）。得到背包的總重量為50+10+30+40+20=150，總價(jià)值為50+40+40+35+20/25*30=189。物品編號(hào)1234567重量wi35306050401025價(jià)值vi10403050354030貪心策略2：重量最輕策略選擇重量最輕的物品，可以裝入盡可能多的物品，從而增加背包的總價(jià)值。但背包的價(jià)值卻不能保證迅速增長(zhǎng)，也不一定能保證裝入背包的物品總價(jià)值達(dá)到最大。按照物品重量從小到大排序，可選擇6號(hào)物品、7號(hào)物品、2號(hào)物品、1號(hào)物品、5號(hào)物品和4號(hào)物品（部分裝入），得到背包的總重量為10+25+30+35+40+10=150，總價(jià)值為40+30+40+10+35+10/50*50=165。物品編號(hào)1234567重量wi35306050401025價(jià)值vi10403050354030貪心策略3：?jiǎn)挝恢亓績(jī)r(jià)值最大策略選擇單位重量?jī)r(jià)值最大的物品，在背包價(jià)值增長(zhǎng)和背包容量消耗兩者之間尋找平衡。將物品按照單位重量?jī)r(jià)格從大到小排序，可選擇6號(hào)物品、2號(hào)物品、7號(hào)物品、4號(hào)物品和5號(hào)物品（部分裝入），得到背包總重量為10+30+25+50+35=150，總價(jià)值為40+40+30+50+35/40*35=190.625。物品編號(hào)1234567重量wi35306050401025價(jià)值vi10403050354030結(jié)論顯然，以上三種貪心策略中，每次選取單位重量?jī)r(jià)值最大策略使得裝入背包的物品總價(jià)值最大。背包問題數(shù)學(xué)模型設(shè)xi表示編號(hào)為i的物品裝入背包情況，0≤xi≤1。根據(jù)問題的要求，有如下目標(biāo)函數(shù)和約束條件：證明貪心策略3正確性首先按照每個(gè)物品的單位重量?jī)r(jià)值vi/wi給物品重新排序，排序后的物品也重新編號(hào)為1~n，即i<j時(shí)有

。貪心策略：從單位重量?jī)r(jià)值最大的物品開始選擇，若將這個(gè)物品全部裝入背包后，背包沒有超過其負(fù)重W，則繼續(xù)選擇下一個(gè)物品進(jìn)行裝入，當(dāng)選擇某物品裝入背包后超過背包負(fù)重，則該物品采用部分裝入方式將背包裝滿。證明貪心策略3正確性（1）存在包含單位價(jià)值最大物品的最優(yōu)解。使用反證法來證明第一步選擇，因?yàn)槲锲芬呀?jīng)按單位重量?jī)r(jià)值遞減排序且w1<W，則部分背包問題存在最優(yōu)解v1x1+v2x2+...+vnxn。若x1=1，顯然最優(yōu)解包含單位重量?jī)r(jià)值最大的物品的結(jié)論成立。若x1<1，則將背包中重量等于(1-x1)w1的部分物品與物品1交換，這樣背包的負(fù)重不變，但因，重樣重量的物品1具有更大的價(jià)值，即等量交換后背包的總價(jià)值增加了，這與假設(shè)是最優(yōu)解矛盾。如果w1≥W，則直接裝入W重的第1個(gè)物品部分即為最優(yōu)解，總價(jià)值為最優(yōu)解包含單位重量?jī)r(jià)值最大的物品的結(jié)論成立!也即，貪心選擇的第一步選擇總是會(huì)包含在某個(gè)最優(yōu)解中。（2）在完成第一步選擇之后，子問題P'()與原問題P()還是同一類問題，意味著我們的選擇沒有改變問題的結(jié)構(gòu)。令π'為子問題P'的最優(yōu)解，π為原問題P的最優(yōu)解，則π=π'+v1。證明貪心策略3正確性證明貪心策略3正確性還是使用反證法來證明這個(gè)結(jié)論，假設(shè)π不是原問題的最優(yōu)解，原問題P的最優(yōu)解為π*。根據(jù)第一步結(jié)論，我們知道最優(yōu)解π*中一定含有v1，那么π*-v1就應(yīng)該是子問題P'的解，π*-v1>π-v1=π'，這與π'為子問題P'的最優(yōu)解定義矛盾。所以π=π'+v1不可能不是最優(yōu)解，因此原問題的最優(yōu)解等于子問題最優(yōu)解加上第一個(gè)選擇的物