第21講_動(dòng)態(tài)規(guī)劃(背包問(wèn)題)

1、ACM-ICPC培訓(xùn)培訓(xùn)投資分配問(wèn)題背包問(wèn)題ACM算法設(shè)計(jì)與分析王建芳ACM-ICPC培訓(xùn)培訓(xùn)投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn) 現(xiàn)有數(shù)量為a（萬(wàn)元）的資金，計(jì)劃分配給n 個(gè)工廠,用于擴(kuò)大再生產(chǎn)。 假設(shè)：xi 為分配給第i 個(gè)工廠的資金數(shù)量（萬(wàn)元）；gi(xi)為第i 個(gè)工廠得到資金后提供的利潤(rùn)值（萬(wàn)元）。 問(wèn)題：如何確定各工廠的資金數(shù)，使得總的利潤(rùn)為最大。 nixaxxgziniiniii.2.1 0)( max11據(jù)此，有下式：河南理工大學(xué)ACM-ICPC培訓(xùn) 令：fk(x) 表示以數(shù)量為x 的資金分配給前k 個(gè)工廠，所得到的最大利潤(rùn)值。 用動(dòng)態(tài)規(guī)劃求解，就是求 fn(a) 的問(wèn)

2、題。 當(dāng) k=1 時(shí)， f1(x) = g1(x) （因?yàn)橹唤o一個(gè)工廠） 當(dāng)1kn 時(shí)，其遞推關(guān)系如下： 設(shè)：y 為分給第k 個(gè)工廠的資金（其中 0y x ），此時(shí)還剩 x y（萬(wàn)元）的資金需要分配給前 k1 個(gè)工廠,如果采取最優(yōu)策略，則得到的最大利潤(rùn)為fk1(xy) ,因此總的利潤(rùn)為： gk(y) fk1(xy) 投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn) nkyxfygxfkkxyk.)()(max)(3210 其中 如果a 是以萬(wàn)元為資金分配單位，則式中的y 只取非負(fù)整數(shù)0，1，2，x。上式可變?yōu)椋?)()(max)(,yxfygxfkkxyk 1210所以，根據(jù)動(dòng)態(tài)規(guī)劃的最優(yōu)化原理，

3、有下式：投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)設(shè)國(guó)家撥給60萬(wàn)元投資，供四個(gè)工廠擴(kuò)建使用，每個(gè)工廠擴(kuò)建后的利潤(rùn)與投資額的大小有關(guān)，投資后的利潤(rùn)函數(shù)如下表所示。依據(jù)題意，是要求 f4(60) 。投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)按順序解法計(jì)算。第一階段：求 f1(x)。顯然有 f1(x) g1(x)，得到下表第二階段：求 f2(x)。此時(shí)需考慮第一、第二個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤(rùn)。 )60()(max)60(1260,10,02yfygfy 投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)12006520605055655080408520850max)0()60()

4、10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最優(yōu)策略為（40，20），此時(shí)最大利潤(rùn)為120萬(wàn)元。同理可求得其它 f2(x) 的值。 )60()(max)60(1260,10,02yfygfy 投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)2210 ,10 ,50212121212121(50)m ax()(50) (0)(50)(10)(40)(20)(30) 105(30)(20)(40)(10)(50)(0)yfgyfygfgfgfgfgfgf最優(yōu)策略為（最優(yōu)策略為（3030，202

5、0），此時(shí)最大利潤(rùn)為），此時(shí)最大利潤(rùn)為105105萬(wàn)元。萬(wàn)元。投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)2210 ,10 ,40(40)m ax()(40)90yfgyfy最優(yōu)策略為（20，20），此時(shí)最大利潤(rùn)為90萬(wàn)元。2210 ,10 ,20 ,30(30)m ax()(30)70yfgyfy最優(yōu)策略為（20，10），此時(shí)最大利潤(rùn)為70萬(wàn)元。投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)2210 ,10 ,20(20)m ax()(20) 50yfgyfy2210 ,10 ,(10)m ax()(10)20yfgyfy最優(yōu)策略為（10，0）或（ 0 ， 10 ） ，此時(shí)最大利潤(rùn)為20萬(wàn)元。

6、 f2(0) 0。最優(yōu)策略為（0，0），最大利潤(rùn)為0萬(wàn)元。 得到下表最優(yōu)策略為（20，0），此時(shí)最大利潤(rùn)為50萬(wàn)元。投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)第三階段：求 f3(x)。此時(shí)需考慮第一、第二及第三個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤(rùn)。 )60()(max)60(2360,10,03yfygfy 投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)1550115201105010070859060105251200max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max23232323232323 fgfgfgfgfg

7、fgfg最優(yōu)策略為（最優(yōu)策略為（20，10，30），最大利潤(rùn)為），最大利潤(rùn)為155萬(wàn)元。萬(wàn)元。同理可求得其它同理可求得其它 f3(x) 的值。得到下表的值。得到下表投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)第四階段：求 f4(60)。即問(wèn)題的最優(yōu)策略。)60()(max)60(3460,10,04yfygfy投資分配問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)16007025656060855011040135251550max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max34343434343434fgfgfgfgfgfgfg最優(yōu)

8、策略為（20，0，30，10），最大利潤(rùn)為160萬(wàn)元。投資分配問(wèn)題ACM-ICPC培訓(xùn)培訓(xùn)背包問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn) 有一個(gè)徒步旅行者，其可攜帶物品重量的限度為有一個(gè)徒步旅行者，其可攜帶物品重量的限度為a 公斤，公斤，設(shè)有設(shè)有n 種物品可供他選擇裝入包中。已知每種物品的重量及種物品可供他選擇裝入包中。已知每種物品的重量及使用價(jià)值（作用），問(wèn)此人應(yīng)如何選擇攜帶的物品（各幾使用價(jià)值（作用），問(wèn)此人應(yīng)如何選擇攜帶的物品（各幾件），使所起作用（使用價(jià)值）最大？件），使所起作用（使用價(jià)值）最大？物品物品 1 2 j n重量（重量（公斤公斤/ /件件） a1 a2 aj an每件使用價(jià)值每件

9、使用價(jià)值 c1 c2 cj cn 這就是背包問(wèn)題。類似的還有工廠里的下料問(wèn)題、運(yùn)輸中的貨物裝載問(wèn)題、人造衛(wèi)星內(nèi)的物品裝載問(wèn)題等。河南理工大學(xué)ACM-ICPC培訓(xùn)o 從每種物品的角度考慮，與它相關(guān)的策略已并非從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取取或不取 兩種，而是有取兩種，而是有取0件、取件、取1件、取件、取2件件等很多種。如果仍然按照解等很多種。如果仍然按照解01背包時(shí)的思背包時(shí)的思路，令路，令fiv表示前表示前i種物品恰放入一個(gè)容量為種物品恰放入一個(gè)容量為v的背包的最大權(quán)的背包的最大權(quán) 值。仍然可以按照每種物品不值。仍然可以按照每種物品不同的策略寫(xiě)出狀態(tài)轉(zhuǎn)移方程，像這樣：同的策

10、略寫(xiě)出狀態(tài)轉(zhuǎn)移方程，像這樣：ofiv=maxfi-1v-k*ci+k*wi|0=k*ci=wi 1=i=wi then m:=f(x-i)+ci;16 if mt then t:=m;17 end;18 f:=t;19 end;20end;2122begin23readln(m,n);24for i:= 1 to n do25 readln(wi,ci);26writeln(f(m);27end.河南理工大學(xué)ACM-ICPC培訓(xùn)o 當(dāng)當(dāng)m不大時(shí)不大時(shí),可以通過(guò)可以通過(guò),但當(dāng)?shù)?dāng)m較大時(shí)較大時(shí),容易超時(shí)，容易超時(shí)，改進(jìn)的遞歸法改進(jìn)的遞歸法 o 改進(jìn)的的遞歸法的思想還是以空間換時(shí)間改進(jìn)的的遞歸法的

11、思想還是以空間換時(shí)間,這只這只要將遞歸函數(shù)計(jì)算過(guò)程中的各個(gè)子函數(shù)的值保存要將遞歸函數(shù)計(jì)算過(guò)程中的各個(gè)子函數(shù)的值保存起來(lái)起來(lái),開(kāi)辟一個(gè)一維數(shù)組即可開(kāi)辟一個(gè)一維數(shù)組即可o 其實(shí)這種以空間換時(shí)間的存儲(chǔ)式搜索就是動(dòng)態(tài)規(guī)其實(shí)這種以空間換時(shí)間的存儲(chǔ)式搜索就是動(dòng)態(tài)規(guī)劃的思想劃的思想河南理工大學(xué)ACM-ICPC培訓(xùn)o 1program knapsack04; 2const maxm=2000;maxn=30; 3type ar=array0.maxn of integer; 4var m,n,j,i,t:integer; 5 c,w:ar; 6 p:array0.maxm of integer; 7funct

12、ion f(x:integer):integer; 8var i,t,m:integer; 9begin10 if px-1 then f:=px /標(biāo)記是標(biāo)記是否計(jì)算過(guò)避免重復(fù)計(jì)算（很重要）否計(jì)算過(guò)避免重復(fù)計(jì)算（很重要）11 else 12 begin1o14 begin15 t:=-1;16 for i:=1 to n do 3 v17 begin18 if x=wi then m:=f(i-wi)+ci;19 if mt then t:=m;20 end;21 px:=t;22 end;23 f:=px;24 end;25end;2627begin28 readln(m,n);29 fo

13、r i:= 1 to n do30 readln(wi,ci);31 fillchar(p,sizeof(p),-1); /搜索中用于存儲(chǔ)各階段的最優(yōu)質(zhì)32 writeln(f(m);33end.ACM-ICPC培訓(xùn)培訓(xùn)0-1背包問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?niiixv1maxnixCxwiniii1,1 , 010-1背包問(wèn)題0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。河南理工大學(xué)ACM-ICPC培訓(xùn)o 有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是ci

14、，價(jià)值是wi。求解將哪些物品裝入背包可使價(jià)值總和最大。o 這是最基礎(chǔ)的背包問(wèn)題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。河南理工大學(xué)ACM-ICPC培訓(xùn)o用子問(wèn)題定義狀態(tài)：即用子問(wèn)題定義狀態(tài)：即fiv表示表示前前i件物品恰放入件物品恰放入(不一定真的是每不一定真的是每個(gè)都放進(jìn)去，而是指最有策略）個(gè)都放進(jìn)去，而是指最有策略）一個(gè)容量為一個(gè)容量為v的背包可以獲得的最大的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：ofiv=maxfi-1v,fi-1v-ci+wio這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題

15、的方程都是由它衍生出來(lái)的。所以有必要將它詳細(xì)解釋一下：衍生出來(lái)的。所以有必要將它詳細(xì)解釋一下：n“將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題 若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問(wèn)題。n如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價(jià)值為fi-1v；n如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-ci的背包中”，此時(shí)能獲得的最大價(jià)值就是fi-1v-ci再加上通過(guò)放入第i件物品獲得的價(jià)值wi。河南理工大學(xué)ACM-ICPC培訓(xùn)o 這個(gè)問(wèn)題非常類似于這個(gè)問(wèn)題非常類似于01背包問(wèn)題，所不同的是每背包問(wèn)題

16、，所不同的是每種物品有無(wú)限件。也就是從每種物品的角度考慮，種物品有無(wú)限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取與它相關(guān)的策略已并非取或不取 兩種，而是有兩種，而是有取取0件、取件、取1件、取件、取2件件等很多種。如果仍然等很多種。如果仍然按照解按照解01背包時(shí)的思路，令背包時(shí)的思路，令fiv表示前表示前i種物品種物品恰放入一個(gè)容量為恰放入一個(gè)容量為v的背包的最大權(quán)的背包的最大權(quán) 值。仍然可值。仍然可以按照每種物品不同的策略寫(xiě)出狀態(tài)轉(zhuǎn)移方程，以按照每種物品不同的策略寫(xiě)出狀態(tài)轉(zhuǎn)移方程，像這樣：像這樣：ofiv=maxfi-1v-k*ci+k*wi|0=k*ci2n時(shí)，算法需要(

17、n2n)計(jì)算時(shí)間。 0-1背包問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)01背包問(wèn)題描述：一個(gè)旅行者有一個(gè)最多能用M公斤的背包，現(xiàn)在有N件物品，它們的重量分別是W1，W2，.,Wn,它們的價(jià)值分別為P1,P2,.,Pn.若每種物品只有一件求旅行者能獲得最大總價(jià)值。河南理工大學(xué)ACM-ICPC培訓(xùn)方式一：遍歷M*N的數(shù)組，對(duì)應(yīng)下圖包的總?cè)萘縈20,物品種類數(shù)N5河南理工大學(xué)ACM-ICPC培訓(xùn)o代碼如下：代碼如下：oconst int nRes=5;/5種物品種物品oint nResWeightnRes+1=0,5,3,4,7,8;/每種物品對(duì)應(yīng)重量每種物品對(duì)應(yīng)重量oint nResValuenRes

18、+1=0,14,6,9,18,20;/每種物品對(duì)應(yīng)價(jià)值每種物品對(duì)應(yīng)價(jià)值oconst int nTotleW=20;/背包容量為背包容量為20oint nValueTablenRes+1nTotleW+1=0;/動(dòng)態(tài)價(jià)值表，每一項(xiàng)對(duì)應(yīng)包當(dāng)前所能裝入的最優(yōu)值動(dòng)態(tài)價(jià)值表，每一項(xiàng)對(duì)應(yīng)包當(dāng)前所能裝入的最優(yōu)值oint KitBag()oofor(int i=1;i=nRes;i+)ofor(int j=1;j=nResWeighti) /當(dāng)包容量大于等于當(dāng)前物品重時(shí)當(dāng)包容量大于等于當(dāng)前物品重時(shí)o/如果裝入當(dāng)前物品所能達(dá)最大價(jià)值如果裝入當(dāng)前物品所能達(dá)最大價(jià)值不裝當(dāng)前物品，包選裝前面物品所能獲得的最大價(jià)值不裝

19、當(dāng)前物品，包選裝前面物品所能獲得的最大價(jià)值o/裝入當(dāng)前物品所能達(dá)最大價(jià)值裝入當(dāng)前物品所能達(dá)最大價(jià)值=當(dāng)前物品價(jià)值當(dāng)前物品價(jià)值+當(dāng)前包容量當(dāng)前包容量j扣除當(dāng)前物品重量后，剩余的容量所能裝入的最大價(jià)值。扣除當(dāng)前物品重量后，剩余的容量所能裝入的最大價(jià)值。o/對(duì)照上表，當(dāng)遍歷到對(duì)照上表，當(dāng)遍歷到i=2,j=8時(shí)，時(shí)，nValueTablei-1j-nResWeighti=nValueTable15=14，滿足條件就裝入物品。，滿足條件就裝入物品。o if(nResValuei+nValueTablei-1j-nResWeightinValueTablei-1j)onValueTableij=nResV

20、aluei+nValueTablei-1j-nResWeighti;/當(dāng)前物品裝入包當(dāng)前物品裝入包.o else/當(dāng)前物品不裝入包，當(dāng)前包容量下的最大價(jià)值仍然是原來(lái)的價(jià)值當(dāng)前物品不裝入包，當(dāng)前包容量下的最大價(jià)值仍然是原來(lái)的價(jià)值onValueTableij=nValueTablei-1j;ooelse/包容量不足以裝入當(dāng)前物品時(shí)，沿用原來(lái)的包容量最大價(jià)值包容量不足以裝入當(dāng)前物品時(shí)，沿用原來(lái)的包容量最大價(jià)值onValueTableij=nValueTablei-1j;o ocout最大值為：最大值為：=nResWeightnR)/包容量大于等于當(dāng)前物品重包容量大于等于當(dāng)前物品重o/獲得物品放入和不

21、放入兩種情況中的價(jià)值最大者獲得物品放入和不放入兩種情況中的價(jià)值最大者nnValueTablenRnW=max(nResValuenR+RecursionBag(nR-1,nW-nResWeightnR),/物品物品入包后的價(jià)值入包后的價(jià)值nRecursionBag(nR-1,nW);/物品不入包的最大價(jià)值物品不入包的最大價(jià)值ooelse/包容量不足以放入當(dāng)前物品包容量不足以放入當(dāng)前物品nnValueTablenRnW=RecursionBag(nR-1,nW);oreturn nValueTablenRnW;o河南理工大學(xué)ACM-ICPC培訓(xùn)o 對(duì)比兩種方式可知，第二種方式遍歷的數(shù)據(jù)量為對(duì)比兩

22、種方式可知，第二種方式遍歷的數(shù)據(jù)量為黃色標(biāo)注結(jié)點(diǎn)，要小于第一種方式的數(shù)據(jù)訪問(wèn)量。黃色標(biāo)注結(jié)點(diǎn)，要小于第一種方式的數(shù)據(jù)訪問(wèn)量。河南理工大學(xué)ACM-ICPC培訓(xùn)o 0-1背包問(wèn)題基本題型：n http:/ 二維費(fèi)用的背包問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)二維背包問(wèn)題的條件可概括為下表 二維費(fèi)用的背包問(wèn)題河南理工大學(xué)ACM-ICPC培訓(xùn)二維背包問(wèn)題可以歸納為如下形式的整數(shù)線性規(guī)劃問(wèn)題： maxc1x1+cixi+cnxn a1x1+aixi+anxna b1x1+bixi+bnxnb xi為非負(fù)整數(shù)，i=1，n正如一維背包問(wèn)題那樣，二維背包問(wèn)題也可以用動(dòng)態(tài)規(guī)劃求解。 二維費(fèi)用的背包問(wèn)題河南理工大學(xué)

23、ACM-ICPC培訓(xùn)二維費(fèi)用的背包問(wèn)題o 問(wèn)題問(wèn)題o 二維費(fèi)用的背包問(wèn)題是指：對(duì)于每件物品，具有二維費(fèi)用的背包問(wèn)題是指：對(duì)于每件物品，具有兩種不同的費(fèi)用；選擇這件物品必須同時(shí)付出這兩種不同的費(fèi)用；選擇這件物品必須同時(shí)付出這兩種代價(jià)；對(duì)于每種代價(jià)都有一個(gè)可付出的最大兩種代價(jià)；對(duì)于每種代價(jià)都有一個(gè)可付出的最大值（背包容量）。問(wèn)怎樣選擇物品可以得到最大值（背包容量）。問(wèn)怎樣選擇物品可以得到最大的價(jià)值。設(shè)這兩種代價(jià)分別為代價(jià)的價(jià)值。設(shè)這兩種代價(jià)分別為代價(jià)1和代價(jià)和代價(jià)2，第，第i件物品所需的兩種代價(jià)分別為件物品所需的兩種代價(jià)分別為ai和和bi。兩種。兩種代價(jià)可付出的最大值（兩種背包容量）分別為代價(jià)可付

24、出的最大值（兩種背包容量）分別為V和和U。物品的價(jià)值為。物品的價(jià)值為wi。河南理工大學(xué)ACM-ICPC培訓(xùn)算法思想o 費(fèi)用加了一維，只需狀態(tài)也加一維即可。設(shè)費(fèi)用加了一維，只需狀態(tài)也加一維即可。設(shè)fivu表示前表示前i件物品付出兩種代價(jià)分別為件物品付出兩種代價(jià)分別為v和和u時(shí)可獲得的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程就是：時(shí)可獲得的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程就是：n fivu=maxfi-1vu,fi-1v-aiu-bi+wi。河南理工大學(xué)ACM-ICPC培訓(xùn)碼頭有一艘載重量為30t，最大容為1210m3的船，由于運(yùn)輸需要,這艘船可用于裝載四種貨物到珠江口，它們的單位體積,重量及價(jià)值量見(jiàn)下表:現(xiàn)求如何裝載這四種

25、貨物使價(jià)值量最大。 河南理工大學(xué)ACM-ICPC培訓(xùn)背包問(wèn)題小結(jié)（1）o 一、01背包o 最簡(jiǎn)單的背包，每件物品選或者不選。for(int i = 1; i = ci; -j) dpj = max(dpj,dpj-ci+ai); 河南理工大學(xué)ACM-ICPC培訓(xùn)o 二、完全背包n 每件物品可以選無(wú)限次for(int i = 1; i = n; +i) for(int j = ci; j = V; +j) dpj = max(dpj,dpj-ci + ai; o 注意：初始化方面的細(xì)節(jié)，如果要求恰好裝滿背包，那么在初始化時(shí)除了dp0為0其它dp1.V均設(shè)為-（求的是最大解，如果求的是最小解，則為

26、） 如果并沒(méi)有要求必須把背包裝滿，而是只希望價(jià)格盡量大，初始化時(shí)應(yīng)該將f0.V全部設(shè)為0。河南理工大學(xué)ACM-ICPC培訓(xùn)o 三、多重背包n每件物品可以選有限次 設(shè)每件物品的個(gè)數(shù)為counti;nO(V*log counti)寫(xiě)法（二進(jìn)制優(yōu)化）for(int i = 1; i = n; +i) int k; for(k = 1; k*2 = k*ci ; -j) dpj = max(dpj,dpj-k*ci + k*ai); k = counti + 1 - k; for(int j = V; j = k*ci; -j) dpj = max(dpj,dpj-k*ci + k*ai); 河南理工

27、大學(xué)ACM-ICPC培訓(xùn)o O(VN)的寫(xiě)法n /*此種方法求最大值不確定可否，但判斷是否能將1-V內(nèi)的背包裝滿可以*/int usedMAXN;for(int i = 1; i = N; +i) memset(used,0,sizeof(used); for(int j = ci; j = V; +j) if(usedj-ci counti & dpj dpj-ci + ai) dpj = dpj-ci + ai; usedj = usedj-ci + 1; /有待驗(yàn)證，估計(jì)不對(duì)，有興趣的可以驗(yàn)證下河南理工大學(xué)ACM-ICPC培訓(xùn)o現(xiàn)在dpi用來(lái)表示容量為i的背包能否被所給物品恰好裝

28、滿 上面的01背包和完全背包以及上面一種O(V*log counti)的寫(xiě)法也可以做這樣的改變memset(dp,false,sizeof(dp);dp0 = true;for(int i = 1; i = N; +i) memset(used,0,sizeof(used); for(int j = ci; j = V; +j) /注意這里是順序的（和完全背包相同），其實(shí)多重背包也可以理解成被限制了的完全背包 if(!dpj & dpj-ci & usedj-ci counti) /注意這里的!dpj不能少 dpj = true; usedj = usedj-ci + 1; 河南理工大學(xué)ACM-ICPC培訓(xùn)o四、混合背包n以上三種背包的混合，有的物品只能取一次，有的物品能取無(wú)限次，有的物品能取有限次算法偽代碼：for i=1.n if 第i件物品是01背包 for j=V.ci dpj=max(); /同上面01背包代碼 else if 第i件物品是完全背包 for j=ci.V dpj=max(); /同上面完全背包 else if 第i件物品是多重背包 MultiplePack(c