學習筆記——背包問題

從良月澪二大佬那學的背包九講

一.01背包問題

衆所周知，01背包是一個較為簡單的DP問題（萬惡之源），從他開始，我們将正式邁入DP的殿堂（死亡的深淵），是以掌握01背包是以後所有背包問題的基礎，需要OIer認真學習。

1.01背包的基本問題描述

有$n$件物品和一個容量為$V$的背包。第i件物品的費用是$w[i]$，價值是$v[i]$，求将哪些物品裝入背包可使價值總和最大。

2.01背包問題的特點：

每種物品僅有一件，可以選擇放或不放。

3.01背包問題的基本思路

設$f[i][j]$表示将前i件物品放入一個容量為j的背包中可以獲得的最大價值。由此可知，其遞推方程式為

f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i])。
           

詳細解釋：将前$i$件物品放入容量為$j$的背包中“這個子問題，若隻考慮第$i$件物品的政策（放或不放），那麼就可以轉化為一個隻牽扯前 $i−1$ 件物品的問題”。如果不放第$i$件物品，“那麼問題就轉化為前 $i−1$ 件物品放入容量為$j$的背包中”，價值為$f [i−1][j]$如果放第$i$件物品，“那麼問題就轉化為前$i−1$件物品放入剩下的容量為$j−w[i]$的背包中”，此時能獲得的最大價值就是 $f[i−1][j-w[i]]$ 再加上通過放入第i件物品獲得的價值$v[i]$。

4.01背包空間複雜度的優化

仔細觀察可知，$f[i][j]$是由$f[i-1][j]$和 $f[i−1][j−w[i]]$ 兩個子問題遞推而來，那我們可以在每次主循環中我們以$j = V->0$的順序推$f[j]$，這樣能保證推$f[j]$時$f[j−w[i]]$儲存的是狀态$f[i−1][j−w[i]]$的值。

注：如果順序推的話，可能會使$f[i][j]$的值覆寫掉$f[i-1][j]$的值，影響我們所要求的真實值，導緻程式出錯。

是以有如下代碼

for (int i = 1; i <= n; i++)
    for (int j = V; j >= 0; j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);
           

其中的 $f[j]=max(f[j],f[j−w[i]])$ 一句恰就相當于我們的轉移方程$f[i][j]=max(f[i−1][j],f[i−1][j−w[i]])$，因為現在的$f[j−w[i]]$就相當于原來的$f[i−1][j−w[i]]$。如果将$V $的循環順序從上面的逆序改成順序的話，那麼則成了$f[i][j]由f[i][j−w[i]]$ 推來，不是我們所要求的值。

其實，這一串代碼還可以優化

for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);
           

顯然可知，當$j<w[i]$時，$f[j]$的狀态時不會改變的，是以隻用讓$j$從$V$循環到$w[i]$即可，減少循環次數。

5.初始化的細節問題

我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。

1.要求恰好裝滿背包時的最優解

這樣的話，在初始化時除了$f[0]$為$0$其它$f[1->V]$均設為 $-$$ \infty $，這樣就可以保證最終得到的$f[N]$是一種恰好裝滿背包的最優解。

解釋：初始化的$f$數組事實上就是在沒有任何物品可以放入背包時的合法狀态。如果要求背包恰好裝滿，那麼此時隻有容量為$0$的背包可能被價值為$0$的$nothing$“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀态，它們的值就都應該為$−$$\infty$了。

2.沒有要求必須把背包裝滿時的最優解

如果背包并非必須被裝滿，那麼任何容量的背包都有一個合法解“什麼都不裝”，這個解的價值為$0$，是以初始時狀态的值也就全部為$0$了。

這個小技巧完全可以推廣到其它類型的背包問題

6.終極優化（防止一些毒瘤出題人卡常）（小bb:應該沒有怎麼喪心病狂的人吧）

前面的代碼中有$for(j=V->w[i])$，還可以将這個循環的下限進行改進。由于隻需要最後$f[j]$的值，倒推前一個物品，其實隻要知道$f[j−w[n]]$即可。以此類推，對以第$j$個背包，其實隻需要知道到$f[j−sum(w[j->n])]$ 即可，即代碼可以改成

for(int i=1;i<=n;i++) cin>>w[i]>>v[i],s[i]=s[i-1]+w[i];
for(int i=1;i<=n;i++){
	int bound=max(w[i],V-(s[n]-s[i]));
	for (int j=V;j>=bound;j--)
		f[j]=max(f[j],f[j-w[i]]+v[i]);
}
           

7.小結

01背包問題是最基本的背包問題，它包含了背包問題中設計狀态、方程的最基本思想。另外，别的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀态轉移方程的意義，以及最後怎樣優化的空間複雜度。

好了，01背包的講解就到這裡吧（反正我也寫不動了）。

來補幾道練手題

1.裸的01背包闆子（01背包詳細教程）（我的代碼）

2.重量=價值的簡單01背包（記得用總重量減去最大價值）（不錯的題解）（我的代碼）

3.求填滿01背包的方案數（新穎的DP題）（思路講解的不錯的題解）（我的代碼）

4.01背包變種--手動求價值（集結了所有背包闆子良心題解）（我的代碼）

5.看似很難實則資料範圍造就白給的水題（以新奇思路優化DP的題解）（我的代碼）

6.多個體積次元的01背包（講的很詳細的題解）（我的代碼）

Update:2020.10.29

二、完全背包問題

1.完全背包問題的基本問題描述

有$N$種物品和一個容量為$V$的背包，每種物品都有無限件可用。第$i$種物品的費用是$w[i]$，價值是$v[i]$。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

2.完全背包問題的特點：

每一件物品都有很多件，可以無限選擇。

3.完全背包問題的基本思路

仍然按照解01背包時的思路，令$f[i][j]$表示前i種物品恰放入一個容量為$V$的背包的最大權值。仍然可以按照每種物品不同的政策寫出狀态轉移方程。

像這樣：

f[i][j]=max(f[i−1][j−k*w[i]]+k*v[i])(0<=k*w[i]<=j)
           

解釋：因為$k$表示選該件物品的次數，是以$k$可以有不選到全部選滿（使背包中再也裝不下該件物品）之間的所有選擇。

這跟01背包問題一樣有$O(VN)$個狀态需要求解，但求解每個狀态的時間已經不是常數了$（O(1)）$。因為求解狀态$f[i][j]$的時間是$O(V/w[i])$，是以總的時間複雜度可以認為是$O(N\times\sum(V/w[i]))$，這個時間複雜度是比較大的。

對于完全背包問題與01背包問題的聯系的感悟：

将01背包問題的基本思路加以改進，得到了這樣一個清晰的解決完全背包問題方法,這說明01背包問題的方程的确是很重要，可以推及其它類型的背包問題。

4.一個常數優化

（一）、若兩件物品$i$、$j$滿足$w[i]\leqslant w[j]$且$v[i]\geqslant v[j]$，則将物品j去掉，不用考慮。

正确性證明：在任何情況下，将一個價值小但費用高的物品換成一個（或多個）價值高且費用低的物品一定能使所求的總價值最高，那這個價值小但費用高的物品就可以不用在循環DP求解時考慮，可以有效的減少循環的次數。

對于一些可能遇到的情況進行分析：

（1）當該資料為随機生成時：因為可能每一個物品都相差很大，是以可以删去大量的無用資料（狀态），大大減少運算量，提高程式運作的效率。

（2）當該資料為（毒瘤）出題人精心（喪心病狂）的構造的時：因為出題人會讓每一個物品都無法被删去，是以無法減少時間複雜度，反而會負優化。

這個優化可以簡單的 $O(n^2)$處理

（二）、首先将費用大于V的物品去掉，然後使用類似計數排序的做法，隻保留費用相同的物品中價值最高的，就可以$O(V+N)$地完成這個優化。

5.将完全背包問題轉化為01背包問題求解

首先，我們腦海中肯定是想将完全背包問題轉化為01背包問題求解（畢竟我們已經學會了01背包問題），那我們可以将一個物品分成$V/w[i]$份（出現了，物品分身術！），再将其用01背包的方法求解。

顯然，這樣做的時間複雜度太大了，那我們可不可以換一種跟快的方法呢？當然可以，畢竟已經有人幫我們想過了（讓我們站在巨人的肩膀上）。

把第i種物品拆成費用為$w[i]\times 2^k$,價值為$v[i]\times 2^k$的$k$件物品，其中$k$滿足$w[i]\times 2^k\le V$。因為不管最優政策選幾件第i種物品，總可以表示成若幹個$2^k$件物品的和。這樣，我們就可以把每種物品拆成$O(log(V/w[i]))$件物品,用二進制的原理降低時間複雜度。

當然，人們還是嫌他太慢了，是以又發明了$O（VN）$的神奇算法。

這個算法使用一維數組，代碼如下

for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= V; j++)
        f[j] = max(f[j], f[j - w[i]] + v[i]);
           

怎麼樣，是不是感覺很簡單？是不是有一種似曾相識的感覺？沒錯，這就是我從01背包問題中的代碼搬過來的（大霧）這就是改了一下j的循環次序，讓j順序查找。

那麼，本着知其然要知其是以然的心态，我們來細細研究一下這其中的妙處。首先，通過回憶01背包，我們可以記得逆序修改是為了讓每一個物品都隻被選一次，那同理可得，順序修改是為了讓DP中該物品有可能被多次選中，這樣既不用讓該物品分身又可以提速，何樂而不為呢？

6.小結

完全背包問題也是一個相當基礎的背包問題，他有以下兩個DP方程式

f[i][j]=max(f[i−1][j−k*w[i]]+k*v[i])(0<=k*w[i]<=j)

for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= V; j++)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

           

需要OIer仔細地體會，不僅記住，也要弄明白他們是怎麼得出來的，最好能夠自己想一種得到這些方程的方法。（了解性記憶肯定比死記硬背更牢固）

事實上，對每一道動态規劃題目都思考其方程的意義以及如何得來，是加深對動态規劃的了解、提高動态規劃功力的好方法。

老規矩，上題。

1.完全背包的闆子題（和01背包闆子一模一樣的題面可還行）（題解）（我的代碼（其實就改一下循環順序，01背包代碼就變成的完全背包代碼））

2.和第一題題面不同的完全背包闆子（講解01背包和完全背包差異的題解）（第一題的代碼（大霧 ）

3.可以通過資料範圍減少DP次數的水題（題解）（我的代碼）

4.要點腦子的完全背包（一語點醒夢中人的題解）（我的代碼）

這道題讓我學會了放慢節奏做題，不要一昧的追求速度，要仔細看清題面。例如本題還要考慮買的多還更便宜的情況。

好了，這個背包的學習筆記将要咕很長一段時間了（别問為什麼，問就是要馬上複習複賽的知識點，考完複賽後還要瘋狂補文化，估計以後要随緣更新了。那麼，有緣再會吧！）

Update 2020.11.24

我又回來了，既然要面對即将到來的NOIP，我當然又停課學OI了。（停課一時爽，月考火葬場）不管怎麼說，還是先開啟我們的背包之旅吧！

三、多重背包問題

1.多重背包問題的基本問題描述

有$N$件物品和一個容量為$V$的背包，第$i$件物品最多有$p[i]$件可用，每一件的費用都是$w[i]$,價值都是$v[i]$。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

2.多重背包問題的特點：

每一件物品都有有限件。

3.多重背包問題的基本思路

數學教遇到新的問題不會怎麼辦？轉化啊！把它變成我們熟悉的01背包不就好了。但是很明顯，如果把每一種物品都拆分成$p[i]$件，那時間複雜度就變成了$O(V \times \sum p[i])$，(這複雜度不得上天)

是以，人們又想到了另一種方法--二進制拆分

4.二進制拆分

方法是：将第$i$種物品分成若幹件物品，其中每件物品有一個系數，這件物品的費用和價值均是原來的費用和價值乘以這個系數。使這些系數分别為$1，2，4$, . . . , $2{k-1}$,$p[i]-2{k}+1$，且$k$是滿足$p[i]-2^{k}+1>0$的最大整數。這樣就将第$i$種物品分成了$O(log(p[i]))$件物品，将原問題轉化為了複雜度為$O(V\times \sum log(p[i]))$的01背包問題。代碼如下

for (int i = 1; i <= n; i++) {
    int num = min(p[i], V / w[i]);//num表示最多可以取的物品數
    for (int k = 1; num > 0; k <<= 1) {//注意，k要不斷*2進行拆分
        if (k > num) k = num;//最後一步防止多取物品，令k為num，這樣可以表示完所有0到num的物品，不重、不漏、不多
        num -= k;//表示完該物品後要将物品總數減去該物品所占物品的數量
        for (int j = V; j >= w[i] * k; j--)//注意轉移時要把系數乘進去
            f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
    }
}
           

5.單調隊列優化

這個算法基于基本算法的狀态轉移方程，但應用單調隊列的方法使每個狀态的值可以以均攤$O(1)$的時間求解。

這個代碼暫時看不懂，是以扔完代碼我就閃了

其實一般不會有毒瘤出題人将時限卡的這麼死，是以掌握好二進制拆分就夠了

//p：某類物品數量，w：某類物品花費，v：某類物品價值，V:商品總價值
void MultiPack(int p, int w, int v) {
    for (int j = 0; j < w; j++) { //j為w的所有組
        int head = 1, tail = 0;
        for (int k = j, i = 0; k <= V / 2; k += w, i++) {
            int r = f[k] - i * v;
            while (head <= tail and r >= q[tail].v) tail--;
            q[++tail] = node(i, r);
            while (q[head].id < i - p) head++; //需要的物品數目
            f[k] = q[head].v + i * v;
        }
    }
}
           

好了，又到了刷題時間

弱化版

1.簡單的多重背包闆子(還沒我跑的快的題解(看思路就好，代碼自己打))(我的代碼)

2.自己定義價值次元的意義的多重背包問題(詳細講解價值次元定義方法的題解)(我的代碼)

注意：對于一些題目不能總想着優化後的代碼，要學會返璞歸真，從最初的思路開始解題。例如本題就不能使用二進制拆分，而要一個一個地枚舉。

求裝滿完全背包的方案數(良心題解，記錄了所有做法(包括搜尋、記搜、DP、滾動數組、一維DP、字首和優化))(我的代碼)

可行性問題

1.統計該容量能否被表示的完全背包問題(講的詳細的題解)(我的代碼)

2.貪心+完全背包問題(一語點醒夢中人的題解)(我的代碼)

經驗教訓：即使對于一些看似簡單的背包題，也要考慮是否夾雜了其他算法。例如本題要使用貪心進行優化，才能得出正确的答案。

二進制優化/單調隊列優化

1.二進制優化的完全背包的闆子(二進制優化的題解)(詳細講解單調隊列優化的題解)(我的代碼)

四、混合背包問題

如果将前面三個背包混合起來，也就是說，有的物品隻可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數有一個上限（多重背包），應該怎麼求解呢？

2.多重背包問題的基本思路

1.01背包+完全背包

考慮到在01背包和完全背包中給出的僞代碼隻有一處不同，故如果隻有兩類物品：一類物品隻能取一次，另一類物品可以取無限次，那麼隻需在對每個物品應用轉移方程時，根據物品的類别選用順序或逆序的循環即可，複雜度是$O(VN)$。(具體一點，就是一類物品隻能取一次，就用逆序的循環，一類物品可以取無限次，就用順序的循環)

2.再加上多重背包

如果再加上有的物品最多可以取有限次，那麼原則上也可以給出$O(VN)$的解法：遇到多重背包類型的物品用單調隊列解即可。但如果不考慮超過$NOIP$範圍的算法的話，用多重背包中将每個這類物品分成$O(log p[i])$個01背包的物品的方法也已經很優了。

p[i]:每個物品的件數，0代表無窮個
for (int i = 1; i <= n; i++)
    if (p[i] == 0)
        for (int j = w[i]; j <= V; j++)
            f[j] = max(f[j], f[j - w[i]] + v[i]);
    else
    for (int k = 1; k <= p[i]; k++)
        for (int j = V; j >= w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + v[i]);
           

在最初寫出這三個過程的時候，可能完全沒有想到它們會在這裡混合應用。這就展現了程式設計中抽象的威力。如果你一直就是以這種 "抽象出過程"的方式寫每一類背包問題的，也非常清楚它們的實作中細微的不同（順序、逆序和二進制拆分），那麼在遇到混合三種背包問題的題目時，一定能很快想到上面簡潔的解法。

小結

有人說，困難的題目都是由簡單的題目疊加而來的，它在本講中已經得到了充分的展現。本來01背包、完全背包、多重背包都不是什麼難題，但将它們簡單地組合起來以後就得到了這樣一道一定能吓倒不少人的題目。但隻要基礎紮實，領會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。

老規矩，上幾道題來練手

1.多重+完全背包(有圖的題解)(我的代碼)

本題也要重新定義價值這一次元，令最少消耗的硬币數為價值，然後在一定範圍内找最小硬币和。

2.01+完全背包問題(詳細的題解)(我的代碼)

本題一定要注意DP的順序，理清思路，按順序寫代碼，不然可能像我一樣被一個DP順序調了一個晚上

五、二維費用背包問題

1.二維費用背包問題的基本問題描述

二維費用的背包問題是指：對于每件物品，具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設這兩種代價分别為代價$1$和代價$2$，第$i$件物品所需的兩種代價分别為$w[i]$和$g[i]$。兩種代價可付出的最大值（兩種背包容量）分别為$V$和$T$。物品的價值為$v[i]$。

2.二維費用背包問題的基本思路

費用加了一維，隻需狀态也加一維即可。設$f[i][j][k]$表示前$i$件物品付出兩種代價分别為$j$和$k$時可獲得的最大價值。狀态轉移方程就是：$f[i][j][k]=max(f[i-1][j][k],f[i-1][j-w[i]][k-g[i]])$

如前述方法，可以隻使用二維的數組：當每件物品隻可以取一次時變量$j$和$k$采用逆序的循環，當物品有如完全背包問題時采用順序的循環，當物品有如多重背包問題時拆分物品。代碼：(假設都為01背包)

for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)
        for (int k = T; k >= g[i]; k--)
            f[j][k] = max(f[j][k], f[j - w[i]][k - g[i]] + v[i]);
           

3.物品總個數的限制

有時，“二維費用”的條件是以這樣一種隐含的方式給出的：最多隻能取$M$件物品。這事實上相當于每件物品多了一種“件數”的費用，每個物品的件數費用均為$1$，可以付出的最大件數費用為$M$。換句話說，設$f[i][j]$表示付出費用$i$、最多選$j$件時可得到的最大價值，則根據物品的類型（01、完全、多重）用不同的方法循環更新，最後在$f[0......V][0......M]$範圍内尋找答案。

4.複數域上的背包問題

另一種看待二維背包問題的思路是：将它看待成複數域上的背包問題。也就是說，背包的容量以及每件物品的費用都是一個複數。而常見的一維背包問題則是實數域上的背包問題。（注意：上面的話其實不嚴謹，因為事實上我們處理的都隻是整數而已。）是以說，一維背包的種種思想方法，往往可以應用于二維背包問題的求解中，因為隻是數域擴大了而已。

扔幾道特别水的例題

1.二維費用背包問題的闆子(題解)(我的代碼)

2.又是一道水題闆子(詳細的題解（話說水題還要題解？）)(我的代碼)

3.再來一道水題闆子（好了好了，之後不刷水題了）(題解)(我的代碼)

4.五維背包+離散化思想的捆綁銷售優惠題(暴力題解（直接五維費用01+完全背包硬剛）)(我的代碼)

六、分組背包問題

1.分組背包問題的基本問題描述

給定$N$組物品，其中第$i$組有$C_i$個物品。第$i$組物品的第$j$個物品的體積為$V_{ij}$，價值為$W_{ij}$。有一個容量為$M$的背包，要求選擇若幹個物品放入背包，使得每組至多選擇一個物品并且物品總體積不超過$M$的前提下，使物品的價值總和最大。

2.分組背包問題的基本思路

這個問題變成了每組物品有若幹種政策：是選擇本組的某一件，還是一件都不選。也就是說設$f[i][j]$表示前$i$組物品花費費用$j$能取得的最大權值，則有：

$$F[i][j]= max \begin{cases} F[i-1][j] \text{不選第i組的物品}\ \max\limits_{1\le k\le C_i}F[i-1][j-V_{ij}]+W_{ik} \text{選第i組的某個物品k}\end{cases}$$

和前面所學的背包問題一樣，我們可以滾掉前一維，用$j$的逆序循環來控制“階段$i$”的狀态隻能由“階段$i-1$”的狀态轉移而來。下面給出代碼：

memset(f,0xcf,sizeof(f));
f[0]=0;
for(int i=1;i<=n;++i)
	for(int j=m;j;--j)
		for(int k=1;k<=c[i];++k)
			if(j>=v[i][k])f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);               
           

其中的$v[i][k]$表示第$i$組物品的第$k$個物品的體積，$w[i][k]$表示第$i$組物品的第$k$個物品的價值。

注意：對于每一組的$c[i]$個物品的循環，$k$應該放在$j$的内層。因為如果$k$在外層，就會産生類似完全背包的效果（上一個物品選完後，這一個物品接着上一個物品的狀态繼續更新導緻錯誤），選擇超過$1$個的物品。

分組背包的例題

1.最裸的闆子(分組背包模闆的題解)(我用另一種處理方式打的代碼)

本題主要考選手如何将物品分組，我選擇浪費一點時間來換取空間，sort一遍後再找物品對應組号進行轉移，題解大部分用空間來換取時間，用二維數組存儲然後進行狀态轉移。

2.隐藏的分組背包(sort用得出神入化的題解)(我的代碼)

本題讓我了解到了sort的新一種用法--對二維數組的某一次元進行排序，就可以極大地降低時間複雜度，友善之後的操作。

七、有依賴背包問題

1.有依賴背包問題的基本問題描述

這種背包問題的物品間存在某種“依賴”的關系。也就是說，$i$依賴于$j$，表示若選物品$i$，則必須選物品$j$。為了簡化起見，我們先設沒有某個物品既依賴于别的物品，又被别的物品所依賴；另外，沒有某件物品同時依賴多件物品。

2.有依賴背包問題的基本思路

這個問題由$NOIP2006$年金明的預算方案一題擴充而來。遵從該題的提法，将不依賴于别的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個問題的簡化條件可知所有的物品由若幹主件和依賴于每個主件的一個附件集合組成。

按照背包問題的一般思路，僅考慮一個主件和它的附件集合。可是，可用的政策非常多，包括：一個也不選，僅選擇主件，選擇主件後再選擇一個附件，選擇主件後再選擇兩個附件…無法用狀态轉移方程來表示如此多的政策。（事實上，設有 $n$個附件，則政策有$2^n+1$個，為指數級。）

考慮到所有這些政策都是互斥的（也就是說，你隻能選擇一種政策），是以一個主件和它的附件集合實際上對應于分組背包中的一個物品組，每個選擇了主件又選擇了若幹個附件的政策對應于這個物品組中的一個物品，其費用和價值都是這個政策中的物品的值的和。但僅僅是這一步轉化并不能給出一個好的算法，因為物品組中的物品還是像原問題的政策一樣多。

再考慮分組背包中的一句話： 可以對每組中的物品應用完全背包中“一個簡單有效的優化”。 這提示我們，對于一個物品組中的物品，所有費用相同的物品隻留一個價值最大的，不影響結果。

是以，我們可以對主件$i$的“附件集合”先進行一次01背包，得到費用依次為$0.....V-c[i]$所有這些值時相應的最大價值$f[0......V-c[i]]$。那麼這個主件及它的附件集合相當于 $V-c[i]+1$個物品的物品組，其中費用為$c[i]+k$的物品的價值為$f'[k]+w[i]$。也就是說原來指數級的政策中有很多政策都是備援的，通過一次01背包後，将主件$i$轉化為$V-c[i]+1$個物品的物品組，就可以直接應用分組背包的算法解決問題了。

3.較一般的問題

更一般的問題是：依賴關系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制隻是每個物品最多隻依賴于一個物品（隻有一個主件）且不出現循環依賴。

解決這個問題仍然可以用将每個主件及其附件集合轉化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能将每個附件都看作一個一般的01背包中的物品了。若這個附件也有附件集合，則它必定要被先轉化為物品組，然後用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。

事實上，這是一種樹形$DP$，其特點是每個父節點都需要對它的各個兒子的屬性進行一次$DP$以求得自己的相關屬性。這已經觸及到了“泛化物品”的思想。看完泛化物品後，你會發現這個“依賴關系樹”每一個子樹都等價于一件泛化物品，求某節點為根的子樹對應的泛化物品相當于求其所有兒子的對應的泛化物品之和。

4.小結

拿金明的預算方案來說，通過引入“物品組”和“依賴”的概念可以加深對這題的了解，還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的依賴關系：物品不能既作主件又作附件，每個主件最多有兩個附件，可以發現一個主件和它的兩個附件等價于一個由四個物品組成的物品組，這便揭示了問題的某種本質。

例題

1.部落格中例子的原題(工程代碼，變量名好評)(我的代碼)

2.樹形DP好題（大霧（記得要用分組背包）(樹形DP的題解)(我的代碼)

八、泛化物品

1.定義

考慮這樣一種物品，它并沒有固定的費用和價值，而是它的價值随着你配置設定給它的費用而變化。這就是泛化物品的概念。

更嚴格的定義是：在背包容量為$V$的背包問題中，泛化物品是一個定義域為$0......V$中的整數的函數$h$，當配置設定給它的費用為$v$時，能得到的價值就是$h(v)$。

這個定義有一點點抽象，另一種了解是一個泛化物品就是一個數組$h[0......V]$，給它費用$v$，可得到價值$h[V]$。

一個費用為$c$價值為$w$的物品，如果它是01背包中的物品，那麼把它看成泛化物品，它就是除了$h(c)=w$其它函數值都為$0$的一個函數。如果它是完全背包中的物品，那麼它可以看成這樣一個函數，僅當$v$被$c$整除時有$h(v)=v / c \times w$，其它函數值均為$0$。如果它是多重背包中重複次數最多為$n$的物品，那麼它對應的泛化物品的函數有$h(v)=v / c \times w$僅當$v$被$c$整除且$v/c \le n$，其它情況函數值均為$0$。一個物品組可以看作一個泛化物品$h$。對于一個$0......V$中的$v$，若物品組中不存在費用為$v$的的物品，則$h(v)=0$，否則$h(v)$為所有費用為$v$的物品的最大價值。有依賴的背包問題中每個主件及其附件集合等價于一個物品組，自然也可看作一個泛化物品。

2.泛化物品的和

如果面對兩個泛化物品$h$和$l$，要用給定的費用從這兩個泛化物品中得到最大的價值，怎麼求呢？事實上，對于一個給定的費用$v$，隻需枚舉将這個費用如何配置設定給兩個泛化物品就可以了。同樣的，對于$0......V$的每一個整數$v$，可以求得費用$v$配置設定到$h$和$l$中的最大價值$f(v)$。也即

$$f(v)=max(h(k)+l(v-k)) (0\leqslant k\leqslant v)$$

可以看到，$f$也是一個由泛化物品$h$和$l$決定的定義域為$0......V$的函數，也就是說，$f$是一個由泛化物品$h$和$l$決定的泛化物品。

由此可以定義泛化物品的和：$h$、$l$都是泛化物品，若泛化物品$f$滿足以上關系式，則稱$f$是$h$與$l$的和。這個運算的時間複雜度取決于背包的容量，是$\Theta (V^2)$。

泛化物品的定義表明：在一個背包問題中，若将兩個泛化物品代以它們的和，不影響問題的答案。事實上，對于其中的物品都是泛化物品的背包問題，求它的答案的過程也就是求所有這些泛化物品之和的過程。設此和為$s$，則答案就是$s[0......V]$中的最大值。

3.背包問題的泛化物品

一個背包問題中，可能會給出很多條件，包括每種物品的費用、價值等屬性，物品之間的分組、依賴等關系等。但肯定能将問題對應于某個泛化物品。也就是說，給定了所有條件以後，就可以對每個非負整數$v$求得：若背包容量為$v$，将物品裝入背包可得到的最大價值是多少，這可以認為是定義在非負整數集上的一件泛化物品。這個泛化物品--或者說問題所對應的一個定義域為非負整數的函數——包含了關于問題本身的高度濃縮的資訊。一般而言，求得這個泛化物品的一個子域（例如$0......V$）的值之後，就可以根據這個函數的取值得到背包問題的最終答案。

綜上所述，一般而言，求解背包問題，即求解這個問題所對應的一個函數，即該問題的泛化物品。而求解某個泛化物品的一種方法就是将它表示為若幹泛化物品的和然後求之。

4.背包問題問法的變化

之前講的都是給定背包容量求其可以得到的最大價值，但其實背包還有很多變化的問題（如最多可以放入幾件物品、最多可以裝滿體積為多少的背包等），需要OIer在做題時随機應變（畢竟學OI最重要的是學會一種思想，然後将這一種思想應用到其他問題中）。

1.輸出方案

我們可以用一個數組記錄下每個狀态的最優值是由狀态轉移方程的哪一項推出來的（它是由那一個決策得到的），然後從最終狀态遞歸的往上一狀态推導，直到回到初始狀态。

以01背包為例：

$$F[i][j]== \begin{cases} F[i-1][j] \text{不選第i組的物品}\ F[i-1][j-V[i]]+W[i] \text{選第i個物品}\end{cases}$$

然後将選擇的物品加入ans數組，再逆序輸出即可。

2.輸出字典序最小的最優方案

首先我們要了解題意--字典序最小指的是選擇的$1......N$号物品的選擇方案排列出來以後字典序最小。

還是以01背包為例子

在該問題中，我們隻用考慮在進行狀态轉移是保證最終選擇的是字典序最小即可，那我們就對狀态轉移方程下手。01背包的狀态轉移方程想必大家都比較熟悉了吧，

$$f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])$$

當$f[i-1][j]=f[i-1][j-w[i]]+v[i]$時，我們一定要選擇目前的物品，這樣就可以保證字典序最小（因為目前物品的編号小于後面物品的編号，與其用後面物品編号大的來組成答案序列，不如先用這個物品編号小的來組成（貪心），反正這個不行後面也會被覆寫掉，這個行就使答案序列的字典序更小了）。

3.求方案總數

簡單來說，就是求将背包裝到某一容量時的方案總數。

對于這一類問題，先将初始化時$f[0][0]=1$，然後将背包問題的狀态轉移方程中$max$轉化為$\sum$即可。還是那01背包當栗子吧

$$f[i][j]=f[i-1][j]+f[i-1][j-w[i]]$$

可行性原因：狀态轉移方程已經考察了所有可能的背包組成方案。

4.最優方案的總數

這裡的最優方案是指物品總價值最大的方案。

還是那個萬年不變的例子（誰讓它最簡單呢）

我們可以再新開一個數組（設為$g[i][j]$），令其記錄$f[i][j]$的最優解方案數（$f[i][j]$由多個狀态都可以得到則$++g[i][j]$，若$f[i][j]$更新為一個新的最大值，則将$g[i][j]$重置為$1$）。

5.求第$K$優解

首先我們要知道，如果該問題的最優解可以寫出DP方程式，那麼該問題的第$K$優解往往可以由同樣的時間複雜度得到，并且在時間上比最優解多一個系數$K$。

思路：将每一個狀态都表示為有序隊列，将狀态轉移方程中的$max$轉化為有序隊列的合并。

還是那個萬年不變的例子（01背包）

因為我們要求的是第$K$優解，是以我們可以在DP數組上新開一維，表示這一狀态的第$K$優解，即$f[i][j][k]$表示用前$i$件物品裝滿容量為$j$的背包的第$K$優解的值。那麼我們的DP方程式也相應變成了

$$f[i][j][k]=max(f[i-1][j][k],f[i-1][j-w[i]][k]+v[i])$$

最終答案為$f[n][m][k]$,時間複雜度為$\Theta(NMK)$。

代碼如下(将政策不同但權值相同的兩個方案是看作同一個解)

int kth(int n, int V, int k) {
    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= w[i]; j--) {
            for (int l = 1; l <= k; l++) {
                a[l] = f[j][l];
                b[l] = f[j - w[i]][l] + v[i];
            }
            a[k + 1] = -1;
            b[k + 1] = -1;
            int x = 1, y = 1, o = 1;
            while (o != k + 1 and (a[x] != -1 or b[y] != -1)) {
                if (a[x] > b[y]) f[j][o] = a[x], x++;
                else f[j][o] = b[y], y++;
                if (f[j][o] != f[j][o - 1]) o++;
            }
        }
    }
    return f[V][k];
}

           

#include <iostream>
#include <cstdio>
#include <complex>
#define A 1000010
using namespace std;
int f[A], w[A], v[A];
/*---------0-1背包----------*/
int knapsack01(int n, int V) {
    memset(f, 0xc0c0c0c0, sizeof f); f[0] = 0; //需要裝滿
    memset(f, 0, sizeof f); //不需要裝滿 
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + v[i]);
    return f[V];
}
/*-----------完全背包----------*/
int Fullbackpack(int n, int V) {
    for (int i = 1; i <= n; i++)
        for (int j = w[i]; j <= V; j++)
            f[j] = max(f[j], f[j - w[i]] + v[i]);
    return f[V];
}
/*-------多重背包二進制拆分-------*/
int number[A];
int MultiplePack1(int n, int V) {
    for (int i = 1; i <= n; i++) {
        int num = min(number[i], V / w[i]);
        for (int k = 1; num > 0; k <<= 1) {
            if (k > num) k = num;
            num -= k;
            for (int j = V; j >= w[i] * k; j--)
            f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
        }
    }
    return f[V];
}
int newv[A], neww[A], cnt;
int MultiplePack2(int n, int V) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= c[i]; j <<= 1) {
            newv[cnt] = j * v[i];
            neww[cnt++] = j * w[i];
            c[i] -= j;
        }
        if (c[i] > 0) {
            newv[cnt] = c[i] * v[i];
            neww[cnt++] = c[i] * w[i];
        }
    }
    for (int i = 1; i <= cnt; i++)
	    for (int j = V; j >= neww[i]; j--)
	        f[j] = max(f[j], f[j - neww[i]] + newv[i]);
	return f[V];
}
/*------------多重背包單調隊列優化------------*/
void MultiPack(int p, int w, int v) {
    for (int j = 0; j < cost; j++) {
        int head = 1,tail = 0;
        for (int k = j, i = 0; k <= V / 2; k += w, i++) {
            int r = f[k] - i * v;
            while (head <= tail and r >= q[tail].v) tail--;
            q[++tail] = node(i, r);
            while (q[head].id < i - num) head++;
            f[k] = q[head].v + i * v;
        }
    }
}
/*-----------二維費用背包----------*/
int t[A], g[A], dp[B][B];
int Costknapsack(int n, int V, int T) {
    for (int i = 1; i <= n; i++)
        for (int j = T; j >= w[i]; j--)
            for (int k = V; k >= g[i]; k--)
                dp[j][k] = max(dp[j][k], dp[j - w[i]][k - g[i]] + v[i]);
	return dp[T][V];
}
/*--------------分組背包--------------*/
int a[B][B];
int Groupingbackpack() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 0; j--)
            for (int k = 1; k <= j; k++)
                f[j] = max(f[j], f[j - k] + a[i][k]);
    return f[m];
}
/*------------K優解---------------*/
int kth(int n, int V, int k) {
	for (int i = 1; i <= n; i++) {
	    for (int j = V; j >= w[i]; j--) {
	  	    for (int l = 1; l <= k; l++) {
	  		    a[l] = f[j][l];
	  		    b[l] = f[j - w[i]][l] + v[i];
			}
			a[k + 1] = -1;
			b[k + 1] = -1;
			int x = 1, y = 1, o = 1;
			while (o != k + 1 and (a[x] != -1 or b[y] != -1)) {
				if (a[x] > b[y]) f[j][o] = a[x], x++;
				else f[j][o] = b[y], y++;
				if (f[j][o] != f[j][o - 1]) o++;
			}
		}
	}
	return f[V][k];
}