1、ACM程序設計,8. 背包初探,2020/7/12,1,Bone Collector,HDOJ 2602 大意 一個容量為V的袋子，N個骨頭，每個有價值和容量，計算你能裝的骨頭的最大價值和。(N = 1000 , V = 1000 ),2020/7/12,2,思路,暴力？ O(2n) 貪心？ 無法得到全局最優(yōu)解 DP？ 狀態(tài)怎么表示？ 狀態(tài)轉(zhuǎn)移是什么？ 初始條件是什么？,2020/7/12,3,經(jīng)典問題（1） 01背包,有N件物品和一個容量為V的背包。放入第i件物品耗費的空間是Ci，得到的價值是Wi。求解將哪些物品裝入背包可使價值總和最大。 特點是每種物品僅有一件，可以選擇放或不放。,2020

2、/7/12,4,定義狀態(tài)：Fiv表示前i件物品放入一個容量為v的背包可以獲得的最大價值。 則其狀態(tài)轉(zhuǎn)移方程便是：,2020/7/12,5,“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只和前i -1件物品相關(guān)的問題。 如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價值為Fi-1v； 如果放第i件物品，那么問題就轉(zhuǎn)化為“前i -1件物品放入剩下的容量為v-Ci的背包中”，此時能獲得的最大價值就是Fi-1v-Ci,再加上通過放入第i件物品獲得的價值Wi。,2020/7/12,6,2020/7/12,7,#de

3、fine V 1111 #define N 1111 #define MAX(x,y) (x)(y)?(x):(y) int dpNV; int cN; int wN; void solve(int n,int v) int i,j; memset(dp,0,sizeof(int)*(v+1); for(i=0;in;i+) for(j=0;jci;j+) dpi+1j = dpij; for(j=ci;j=v;j+) dpi+1j = MAX(dpij,dpij-ci+wi); ,時間復雜度O(NV) 空間復雜度O(NV),空間復雜度的優(yōu)化,空間復雜度卻可以優(yōu)化到O(V) 數(shù)組fV，能不能保

4、證第i次循環(huán)結(jié)束后fv中表示Fiv呢？ Fiv是由Fi-1v和Fi-1v-Ci兩個子問題遞推而來，能否保證在計算Fiv時（也即在第i次主循環(huán)中計算fv時）能夠取用Fi-1v和Fi-1v-Ci的值呢？ 每次主循環(huán)中我們以v = V.0的遞減順序計算Fv，這樣第i次循環(huán)時，在計算前，fv表示Fi-1v,fv-Ci保存的是Fi-1v-Ci的值。,2020/7/12,8,2020/7/12,9,#define V 1111 #define N 1111 #define MAX(x,y) (x)(y)?(x):(y) int dpV; int cN; int wN; void solve(int n,i

5、nt v) int i,j; memset(dp,0,sizeof(int)*(v+1); for(i=0;i=ci;j-) dpj = MAX(dpj,dpj-ci+wi); ,時間復雜度O(NV) 空間復雜度O(maxN,V),I NEED A OFFER!,HDU 1203 大意 N元錢，M個學校，每個學校的申請費為Ai,通過概率是Bi 求獲得offer的最大概率,2020/7/12,10,思路,很明顯一個01背包 變化在于狀態(tài)轉(zhuǎn)移 Fiv表示前i個學校，花v元錢申請的最大通過率 Fiv = maxFi-1v, Wi+(1-Wi)Fi-1v-Ci F00.V = 0 同樣可以使用前面的技

6、巧，降低空間復雜度,2020/7/12,11,2020/7/12,12,#define V 11111 #define N 1111 #define MAX(x,y) (x)(y)?(x):(y) double dpV; int cN; double wN; void solve(int n,int v) int i,j; memset(dp,0,sizeof(double)*(v+1); for(i=0;i=ci;j-) dpj = MAX(dpj,wi+(1.0-wi)*dpj-ci); ,兩種問法,要求“恰好裝滿背包”時的最優(yōu)解 要求必須把背包裝滿 區(qū)別這兩種問法的實現(xiàn)方法是在初始化的時

7、候有所不同。 要求恰好裝滿背包，那么在初始化時除了F0為0，其它F1.V均設為-INF，這樣就可以保證最終得到的FV是一種恰好裝滿背包的最優(yōu)解。 沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將F0.V全部設為0。,2020/7/12,13,初始化的F數(shù)組事實上就是在沒有任何物品可以放入背包時的合法狀態(tài)。 如果要求背包恰好裝滿，那么此時只有容量為0的背包可以在什么也不裝且價值為0的情況下被“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)，應該被賦值為-了。 如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”，這個解的價值為0，所以初始時狀態(tài)的值也就全

8、部為0了。,2020/7/12,14,Piggy Bank,POJ 1384 存錢罐容量V為F-E，有n種硬幣，每種硬幣的價值為Wi，容量為Ci。問組成的硬幣的最小價值和。 V=10000,n=500,Wi=50000,Ci=10000,2020/7/12,15,完全背包問題,有N種物品和一個容量為V的背包，每種物品都有無限件可用。放入第i種物品的耗費的空間是Ci，得到的價值是Wi。 求解：將哪些物品裝入背包，可使這些物品的耗費的空間總和不超過背包容量，且價值總和最大。,2020/7/12,16,基本思路,這個問題非常類似于01背包問題，所不同的是每種物品有無限件。 從每種物品的角度考慮，與它

9、相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件直至取V/Ci件等很多種。,2020/7/12,17,如果仍然按照解01背包時的思路，令Fiv表示前i種物品恰放入一個容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣： 求解狀態(tài)Fi,v的時間是O(V/Ci) 總的時間復雜度為,2020/7/12,18,簡單的優(yōu)化,若兩件物品i、j滿足Ci=Wj，則將可以將物品j直接去掉，不用考慮。 優(yōu)化操作的時間復雜度O(NlogN) 首先將費用大于V的物品去掉，然后使用類似計數(shù)排序的做法，計算出費用相同的物品中價值最高的是哪個，可以O(V+N)地完成這個優(yōu)化,2020

10、/7/12,19,轉(zhuǎn)化為01背包問題求解,最簡單的想法是，考慮到第i種物品最多選V/Ci件，于是可以把第i種物品轉(zhuǎn)化為V/Ci件費用及價值均不變的物品，然后求解這個01背包問題。 時間復雜度沒有變化 二進制優(yōu)化 把第i種物品拆成費用為Ci*2k、價值為Wi*2k的若干件物品，其中k取遍滿足Ci*2k =V 的非負整數(shù)。 時間復雜度,2020/7/12,20,TLE,void solve(int n,int v) int i,j,ck,wk; dp0 = 0; for(i=1;i=ck;j-) dpj = MIN(dpj,dpj-ck+wk); ,2020/7/12,21,AC,void sol

11、ve(int n,int v) int i,j,ck,wk; dp0 = 0; for(i=1;i=ck;j-) dpj = MIN(dpj,dpj-ck+wk); ,2020/7/12,22,悼念512汶川大地震遇難同胞珍惜現(xiàn)在，感恩生活,HDU 2191 n元錢，m種大米，每種大米每袋單價pi，重量hi，總數(shù)ci 求最多買多少大米 n=100,m=100,pi=20,hi=200,ci=20,2020/7/12,23,經(jīng)典問題（3）多重背包,有N種物品和一個容量為V的背包。 第i種物品最多有Mi件可用，每件耗費的空間是Ci，價值是Wi。 求解將哪些物品裝入背包可使這些物品的耗費的空間總和不

12、超過背包容量，且價值總和最大。,2020/7/12,24,這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改即可。,2020/7/12,25,轉(zhuǎn)化為01背包問題,把第i種物品換成Mi件01背包中的物品，則得到了物品數(shù)為sum(Mi)的01背包問題。 二進制優(yōu)化 將第i種物品分成若干件01背包中的物品，其中每件物品有一個系數(shù)。這件物品的費用和價值均是原來的費用和價值乘以這個系數(shù) 令這些系數(shù)分別為1,2,22 ,2k-1;Mi-2k + 1，且k是滿足Mi-2k + 1 0的最大整數(shù)。 M=13,分成1,2,4,6,2020/7/12,26,2020/7/12,27,void

13、solve(int n,int v) int i,j,ck,wk,k,mk; for(i=0;i0;k=ck;j-) dpj = MAX(dpj,dpj-ck+wk); ,更多的變形,推薦看背包九講 本slides大量參考背包九講，在此鳴謝其作者崔添翼,2020/7/12,28,課后作業(yè),HDU WEB-DIY 5012 2013 湘潭大學 ACM程序設計作業(yè)8 開始時間2013-06-08 14:00:00 結(jié)束時間2013-06-29 14:00:00 密碼：xtuacm2013,29,2013年暑假集訓隊選拔,1. 入隊標準A. 2012年獲得Regional銅獎或以上成績隊員B. Codeforces的第三高Rating為1600分以上隊員C. 通過2+1選拔賽的隊員 2. 隊伍人數(shù)30人,2020/7/12,30,報名表格見群郵件，填好發(fā)送到 ,2013年暑假集訓隊選拔,3. 2+1選拔賽地點為工科樓6樓計算機系機房,個人賽場次 時間 1 2013-7-7 上午9點12點 2 2013-7-7 下午3點