uestc08暑假集訓(xùn)背包講義類

1、基礎(chǔ)問題:01背包有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是ci，價(jià)值是wi。求解將哪些物品裝入背包可使價(jià)值總和最大。特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。 狀態(tài)轉(zhuǎn)移方程fiv=maxfi-1v,fi-1v-ci+wi初始化:(1) 不要求背包放滿for v=0V f0v=0; (2)要求背包放滿f00為0其它f01.V均設(shè)為-時(shí)間和空間復(fù)雜度均為O(VN)優(yōu)化空間復(fù)雜度（二維轉(zhuǎn)一維） for i=1.N for v=V.0 （不是） fv=maxfv,fv-ci+wi; 在每次主循環(huán)中fv保存著fi-1v的值由于費(fèi)用為cost的物品不會(huì)影響狀態(tài)f0.cos1，因?yàn)檠b不下。 vo

2、id ZeroOne(int cost,int weight)/處理一個(gè)物品int v;for(v=V;v=cost;v-) fv=max(fv,fv-cost+weight); for(i=1;i=n;i+)/處理所有物品ZeroOne(ci,wi);完全背包問題每種物品都有無限件可用方程：fiv=maxfi-1v-k*ci+k*wi|0=k*ci=v每件物品并非取或不取兩種，而是有取0件、取1件、取2件等很多種。求解狀態(tài)fiv的時(shí)間是O(v/ci)，總的復(fù)雜度可以認(rèn)為是O(V*(V/ci)，需要優(yōu)化 一個(gè)簡(jiǎn)單有效的優(yōu)化若兩件物品i、j滿足ci=wj，則將物品j去掉，不用考慮。需要O(N2)

3、的時(shí)間 另一個(gè)思路：轉(zhuǎn)化為01背包問題求解 即：將一種物品拆成多件物品。更高效的轉(zhuǎn)化方法把第i種物品拆成費(fèi)用為ci*2k、價(jià)值為wi*2k的若干件物品，其中k滿足ci*2k=V。但我們有更優(yōu)的O(VN)的算法。 for i=1.N for v=0.V fv=maxfv,fv-cost+weight 這個(gè)偽代碼與01背包的偽代碼只有v的循環(huán)次序相反而已 第i次循環(huán)中fv保存了i物品已成為入選可能時(shí)最大狀態(tài) 值得一提的是，上面的偽代碼中兩層for循環(huán)的次序可以顛倒。這個(gè)結(jié)論有可能會(huì)帶來算法時(shí)間常數(shù)上的優(yōu)化。void Complete(int cost,int weight) )/處理一個(gè)物品int

4、 v;for(v=cost;v=V;v+)(cost理由同01） fv=max(fv,fv-cost+weight);for(i=1;i=n;i+)/處理所有物品Complete (ci,wi);多重背包問題第i種物品最多有ni件可用 基本算法:和完全背包問題很類似。對(duì)于第i種物品有ni+1種策略：取0件，取1件取ni件。狀態(tài)轉(zhuǎn)移方程：fiv=maxfi-1v-k*ci+k*wi|0=k0的最大整數(shù)。例如，如果ni為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。這樣就將第i種物品分成了O(log ni)種物品將原問題轉(zhuǎn)化為了復(fù)雜度為O(V*log ni)的01背包問題， 偽代碼：處

5、理一個(gè)物品MultiplePack(cost,weight,amount) if cost*amount=V Complete (cost,weight) else k=1 while k=V)Complete(cost,weight);else int k=1;while(kamount)ZeroOne(cost*k,weight*k);amount-=k;k*=2;ZeroOne(cost*amount,weight*amount);for(i=1;i=n;i+) Multiple(ci,ci,amounti);看一道題Poj 1276有一臺(tái)ATM機(jī)，有N種鈔票，第k種鈔票有Dk張，每張nk元。給一個(gè)數(shù)cash,問由這些鈔票組合最多能達(dá)到多少元（不超過cash)這是一道標(biāo)準(zhǔn)的多重背包問題套用Multiple（）函數(shù)N次，即可。一個(gè)小小的思考：每個(gè)物品cost是什么，weight是什么背包還有很多變化混合三種背包問題 二維費(fèi)用的背