4 混合三種背包問(wèn)題
4.1 問(wèn)題
如果將前面1、2、3中的三種背包問(wèn)題混合起來(lái)。也就是說(shuō)，有的物品只可以取一次（01 背包），有的物品可以取無(wú)限次（完全背包），有的物品可以取的次數(shù)有一個(gè)上限（多重背包）。應(yīng)該怎么求解呢？
4.2 01 背包與完全背包的混合
考慮到01 背包和完全背包中給出的偽代碼只有一處不同，故如果只有兩類(lèi)物品：一類(lèi)物品只能取一次，另一類(lèi)物品可以取無(wú)限次，那么只需在對(duì)每個(gè)物品應(yīng)用轉(zhuǎn)移方程時(shí)，根據(jù)物品的類(lèi)別選用順序或逆序的循環(huán)即可，復(fù)雜度是O(V N)。偽代碼如下：
4.3 再加上多重背包
如果再加上最多可以取有限次的多重背包式的物品，那么利用單調(diào)隊(duì)列，也可以給出均攤O(V N) 的解法。
但如果不考慮單調(diào)隊(duì)列算法的話(huà)，用將每個(gè)這類(lèi)物品分成O(logMi) 個(gè)01 背包的物品的方法也已經(jīng)很優(yōu)了。
最清晰的寫(xiě)法是調(diào)用我們前面給出的三個(gè)過(guò)程。
在下一章的末尾我會(huì)用一到例題來(lái)實(shí)現(xiàn)這個(gè)三種背包混合的偽代碼
在最初寫(xiě)出這三個(gè)過(guò)程的時(shí)候，可能完全沒(méi)有想到它們會(huì)在這里混合應(yīng)用。我想這體現(xiàn)了編程中抽象的威力。如果你一直就是以這種“抽象出過(guò)程”的方式寫(xiě)每一類(lèi)背包問(wèn)題的，也非常清楚它們的實(shí)現(xiàn)中細(xì)微的不同，那么在遇到混合三種背包問(wèn)題的題目時(shí)，一定能很快想到上面簡(jiǎn)潔的解法，對(duì)嗎？
4.4 小結(jié)
有人說(shuō)，困難的題目都是由簡(jiǎn)單的題目疊加而來(lái)的。這句話(huà)是否公理暫且存之不論，但它在本講中已經(jīng)得到了充分的體現(xiàn)。本來(lái)01 背包、完全背包、多重背包都不是什么難題，但將它們簡(jiǎn)單地組合起來(lái)以后就得到了這樣一道一定能?chē)樀共簧偃说念}目。但只要基礎(chǔ)扎實(shí)，領(lǐng)會(huì)三種基本背包問(wèn)題的思想，就可以做到把困難的題目拆分成簡(jiǎn)單的題目來(lái)解決。
5 二維費(fèi)用的背包問(wèn)題
5.1 問(wèn)題
二維費(fèi)用的背包問(wèn)題是指：對(duì)于每件物品，具有兩種不同的費(fèi)用，選擇這件物品必須同時(shí)付出這兩種費(fèi)用。對(duì)于每種費(fèi)用都有一個(gè)可付出的最大值（背包容量）。問(wèn)怎樣選擇物品可以得到最大的價(jià)值。設(shè)第i 件物品所需的兩種費(fèi)用分別為Ci 和Di。兩種費(fèi)用可付出的最大值（也即兩種背包容量）分別為V 和U。物品的價(jià)值為Wi。
5.2 算法
費(fèi)用加了一維，只需狀態(tài)也加一維即可。設(shè)F[i, v, u] 表示前i 件物品付出兩種費(fèi)用分別為v 和u 時(shí)可獲得的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程就是：
如前述優(yōu)化空間復(fù)雜度的方法，可以只使用二維的數(shù)組：當(dāng)每件物品只可以取一次時(shí)變量v 和u 采用逆序的循環(huán)，當(dāng)物品有如完全背包問(wèn)題時(shí)采用順序的循環(huán)，當(dāng)物品有如多重背包問(wèn)題時(shí)拆分物品。這里就不再給出偽代碼了，相信有了前面的基礎(chǔ)，讀者應(yīng)該能夠自己實(shí)現(xiàn)出這個(gè)問(wèn)題的程序。
本章末尾會(huì)有一道例題實(shí)現(xiàn)二維費(fèi)用背包的這段偽代碼
5.3 物品總個(gè)數(shù)的限制
有時(shí)，“二維費(fèi)用”的條件是以這樣一種隱含的方式給出的：最多只能取U 件物品。這事實(shí)上相當(dāng)于每件物品多了一種“件數(shù)”的費(fèi)用，每個(gè)物品的件數(shù)費(fèi)用均為1，可以付出的最大件數(shù)費(fèi)用為U。換句話(huà)說(shuō)，設(shè)F[v,u] 表示付出費(fèi)用v、最多選u 件時(shí)可得到的最大價(jià)值，則根據(jù)物品的類(lèi)型（01、完全、多重）用不同的方法循環(huán)更新，最后在f[0 ... V, 0...U] 范圍內(nèi)尋找答案。
5.4 二維整數(shù)域N2 上的背包問(wèn)題
另一種看待二維背包問(wèn)題的思路是：將它看待成N2 域上的背包問(wèn)題。也就是說(shuō)，背包的容量以及每件物品的費(fèi)用都是一個(gè)二維向量。而常見(jiàn)的一維背包問(wèn)題則是自然數(shù)域上的背包問(wèn)題。所以說(shuō)，一維背包的種種思想方法，往往可以應(yīng)用于二位背包問(wèn)題的求解中，因?yàn)橹皇菙?shù)域擴(kuò)大了而已。作為這種思想的練習(xí)，你可以嘗試將后文中提到的“子集和問(wèn)題”擴(kuò)展到二維，并試圖用同樣的復(fù)雜度解決。
5.5 小結(jié)
當(dāng)發(fā)現(xiàn)由熟悉的動(dòng)態(tài)規(guī)劃題目變形得來(lái)的題目時(shí)，在原來(lái)的狀態(tài)中加一維以滿(mǎn)足新的限制是一種比較通用的方法。希望你能從本講中初步體會(huì)到這種方法。
例題來(lái)了，這道例題結(jié)合了混合背包和二維費(fèi)用背包。所以用這一道題把之前說(shuō)的兩部分偽代碼做一下實(shí)現(xiàn)，那么我們接下來(lái)看一看題目以及題目的代碼實(shí)現(xiàn)部分
題目：
Problem Description
暗黑游戲中，裝備直接決定玩家人物的能力?？梢允褂肞g和Rune購(gòu)買(mǎi)需要的物品。暗黑市場(chǎng)中的裝備，每件有不同的價(jià)格(Pg和Rune)、能力值、最大可購(gòu)買(mǎi)件數(shù)。Kid作為暗黑戰(zhàn)網(wǎng)的一個(gè)玩家，當(dāng)然希望使用盡可能少的Pg和Rune購(gòu)買(mǎi)更優(yōu)的裝備，以獲得最高的能力值。請(qǐng)你幫忙計(jì)算出現(xiàn)有支付能力下的最大可以獲得的能力值。
Input
輸入有多組數(shù)據(jù)，每組數(shù)據(jù)的首行三個(gè)整數(shù)N(0<N<=150),P(0<P<=100),R(0<R<=100)，分別代表市場(chǎng)中物品的種類(lèi)，Pg的支付能力和Rune的支付能力。第2至N+1行，每行四個(gè)整數(shù)，前兩個(gè)整數(shù)分別為購(gòu)買(mǎi)此物品需要花費(fèi)的Pg和Rune，第三個(gè)整數(shù)若為0，則說(shuō)明此物品能購(gòu)買(mǎi)無(wú)數(shù)件，若為其他數(shù)字，則此物品可購(gòu)買(mǎi)的最多件數(shù)(0<=S<=32)，第四個(gè)整數(shù)為該裝備的能力值。
Output
對(duì)于每組數(shù)據(jù)輸出一個(gè)整數(shù)，最大可獲得的能力值。
Sample Input
3 10 105 3 0 1104 3 4 1202 3 1 130
Sample Output
370
思路分析：我們可以看到題目中可以使用pg和rune兩個(gè)支付手段去支付裝備，那么這里級(jí)可以抽象成二維費(fèi)用，能力值就是背包的價(jià)值。最大可購(gòu)買(mǎi)件數(shù)就是物品的數(shù)量。題目中的描述當(dāng)物品數(shù)為0時(shí)代表無(wú)限件,這里可以抽象成完全背包問(wèn)題，當(dāng)物品件數(shù)為1時(shí)則可以抽象成01背包問(wèn)題。當(dāng)物品件數(shù)為除了0和1之外的值時(shí)變可以抽象成多重背包問(wèn)題。所以這道題是典型的二維費(fèi)用背包+混合背包的問(wèn)題。那么接下來(lái)我們看看代碼實(shí)現(xiàn)
#include <iostream>
using namespace std;
const int N=150;
const int P=5000;
int pg[N+1]; //pg支付費(fèi)用
int rune[N+1]; //rune支付費(fèi)用
int dp[P+1][P+1]; //dp[i][j]=k 表示花費(fèi)pg為i rune為j時(shí)的最大價(jià)值為k
int s[N+1]; // 件數(shù)
int v[N+1]; //能力值
int max(int a,int b)
{
return a>b?a:b;
}
void ZeroOnePack(int dp[][P+1],int weight_1,int weight_2,int total_1,int total_2,int value)
{
int j,i;
for(i=total_1;i>=weight_1;i--)
{
for(j=total_2;j>=weight_2;j--)
{
dp[i][j]=max(dp[i][j],dp[i-weight_1][j-weight_2]+value);
}
}
}
void completePack(int dp[][P+1],int weight_1,int weight_2,int total_1,int total_2,int value)
{
int j,i;
for(i=weight_1;i<=total_1;i++)
{
for(j=weight_2;j<=total_2;j++)
{
dp[i][j]=max(dp[i][j],dp[i-weight_1][j-weight_2]+value);
}
}
}
void mutiPack(int dp[][P+1],int weight_1,int weight_2,int total_1,int total_2,int amount,int value)
{
if(amount*weight_1>total_1&&amount*weight_2>total_2)
{
completePack(dp,weight_1,weight_2,total_1,total_2,value);
}
else
{
int k=1;
while(amount-k>=0)
{
ZeroOnePack(dp,k*weight_1,k*weight_2,total_1,total_2,k*value);
amount-=k;
k*=2;
}
ZeroOnePack(dp,amount*weight_1,amount*weight_2,total_1,total_2,amount*value);
}
}
int main()
{
int n,P,R;
cin>>n>>P>>R;
int i;
int p,r,num,val;
for(i=0;i<n;i++)
{
cin>>p>>r>>num>>val;
pg[i]=p;
rune[i]=r;
s[i]=num;
v[i]=val;
}
for(i=0;i<n;i++)
{
if(s[i]==1)//01 背包
{
ZeroOnePack(dp,pg[i],rune[i],P,R,v[i]);
}
else if(s[i]==0)// 完全背包
{
completePack(dp,pg[i],rune[i],P,R,v[i]);
}
else //多重背包
{
mutiPack(dp,pg[i],rune[i],P,R,s[i],v[i]);
}
}
cout<<dp[P][R]<<endl;
return 0;
}
6 分組的背包問(wèn)題
6.1 問(wèn)題
有N 件物品和一個(gè)容量為V 的背包。第i 件物品的費(fèi)用是Ci，價(jià)值是Wi。這些物品被劃分為K 組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。
6.2 算法
這個(gè)問(wèn)題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說(shuō)設(shè)F[k, v] 表示前k 組物品花費(fèi)費(fèi)用v 能取得的最大權(quán)值，則有：
使用一維數(shù)組的偽代碼如下：
這里三層循環(huán)的順序保證了每一組內(nèi)的物品最多只有一個(gè)會(huì)被添加到背包中。
另外，顯然可以對(duì)每組內(nèi)的物品應(yīng)用2.3中的優(yōu)化。
6.3 小結(jié)
分組的背包問(wèn)題將彼此互斥的若干物品稱(chēng)為一個(gè)組，這建立了一個(gè)很好的模型。不少背包問(wèn)題的變形都可以轉(zhuǎn)化為分組的背包問(wèn)題（例如7），由分組的背包問(wèn)題進(jìn)一步可定義“泛化物品”的概念，十分有利于解題。
下面拿了2道和分組背包有關(guān)的題目來(lái)當(dāng)例子實(shí)踐偽代碼
第一道： HDU 1712
ACboy needs your help
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7535 Accepted Submission(s): 4164
Problem Description
ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.
Output
For each data set, your program should output a line which contains the number of the max profit ACboy will gain.
Sample Input
2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0
Sample Output
3
4
6
這道題就是很典型的可以抽象成分組背包的問(wèn)題，每門(mén)課代表一種物品，所有的天數(shù)代表背包容量。然后每門(mén)課準(zhǔn)備上的天數(shù)代表在這門(mén)課中所有可能的值。一門(mén)課就是一個(gè)組，并且每組內(nèi)的物品互相沖突，比如你選擇了A課上2天就不能再選擇A課上1天。組內(nèi)互斥，每組最多選一個(gè)。下面看看代碼實(shí)現(xiàn);
#include<iostream>
using namespace std;
const int N=100;
int a[N+1][N+1]; //a[i][j]=k 代表第i門(mén)課上j天所獲得的價(jià)值為k
int dp[N+1];
//分組背包問(wèn)題 每組最多拿一個(gè) 最典型分組背包
int main()
{
int n,m;
cin>>n>>m;
while(n!=0&&m!=0)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(i=1;i<=n;i++)//n門(mén)課
{
for(j=m;j>=1;j--)//所擁有的天數(shù)
{
for(int k=1;k<=m;k++)//第i門(mén)課 的課程時(shí)間 每門(mén)課有多個(gè)課程時(shí)間 存儲(chǔ)在二維數(shù)組a中
{
if(j-k>=0&&dp[j]<dp[j-k]+a[i][k])
{
dp[j]=dp[j-k]+a[i][k];
}
}
}
}
cout<<dp[m]<<endl;
memset(dp,0,sizeof(dp));
cin>>n>>m;
}
return 0;
}
第二道： HDU 3033
I love sneakers!
**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5718 Accepted Submission(s): 2344**
Problem Description
After months of hard working, Iserlohn finally wins awesome amount of scholarship. As a great zealot of sneakers, he decides to spend all his money on them in a sneaker store.
There are several brands of sneakers that Iserlohn wants to collect, such as Air Jordan and Nike Pro. And each brand has released various products. For the reason that Iserlohn is definitely a sneaker-mania, he desires to buy at least one product for each brand.
Although the fixed price of each product has been labeled, Iserlohn sets values for each of them based on his own tendency. With handsome but limited money, he wants to maximize the total value of the shoes he is going to buy. Obviously, as a collector, he won’t buy the same product twice.Now, Iserlohn needs you to help him find the best solution of his problem, which means to maximize the total value of the products he can buy.
Input
Input contains multiple test cases. Each test case begins with three integers 1<=N<=100 representing the total number of products, 1 <= M<= 10000 the money Iserlohn gets, and 1<=K<=10 representing the sneaker brands. The following N lines each represents a product with three positive integers 1<=a<=k, b and c, 0<=b,c<100000, meaning the brand’s number it belongs, the labeled price, and the value of this product. Process to End Of File.
Output
For each test case, print an integer which is the maximum total value of the sneakers that Iserlohn purchases. Print "Impossible" if Iserlohn's demands can’t be satisfied.
Sample Input
5 10000 31 4 62 5 73 4 991 55 772 44 66
Sample Output
255
這道題也是分組背包問(wèn)題的代表，只不過(guò)和上一道有一點(diǎn)不一樣的是，每組內(nèi)至少拿一件物品。我們來(lái)看，一個(gè)品牌代表一個(gè)組，所擁有的錢(qián)代表背包容量，每個(gè)品牌里面的鞋子產(chǎn)品代表這個(gè)組內(nèi)的物品成員。
dp[i][j] 代表前i個(gè)品牌鞋子花費(fèi)j元 所獲得的最大價(jià)值
這道題的初始化可能稍微有點(diǎn)變化，因?yàn)槿绻跏蓟痙p為0則無(wú)法區(qū)分是買(mǎi)不全那幾款鞋子還是能買(mǎi)全但最大價(jià)值是0，因?yàn)槲覀冊(cè)谫I(mǎi)不全的時(shí)候需要輸出特殊字符。而在之前的01背包問(wèn)題等其他問(wèn)題時(shí)，只需要計(jì)算最大價(jià)值即可，所以為0并不影響結(jié)果。
這道題的狀態(tài)轉(zhuǎn)移方程：
- dp[i][k]是不選擇當(dāng)前鞋子；
- dp[i-1][k-v[j]]+w[j]是選擇當(dāng)前鞋子，但是是第一次在本組中選，由于開(kāi)始將該組dp賦為了-1，所以第一次取時(shí)，必須由上一組的結(jié)果推知，這樣才能保證得到全局最優(yōu)解；
- dp[i][k-v[j]]+w[j]表示選擇當(dāng)前鞋子，并且不是第一次在本組中取。
代碼實(shí)現(xiàn):
#include <iostream>
using namespace std;
const int N=100;
const int Max_brand=10;
const int Max_money=10000;
int s[N+1];// 鞋子的品牌數(shù)組
int v[N+1];// 鞋子的價(jià)值數(shù)組
int c[N+1];// 鞋子的費(fèi)用數(shù)組
int dp[Max_brand+1][Max_money+1]; //dp[i][j] 代表購(gòu)買(mǎi)前i組品牌鞋子花費(fèi)j元所得到的最大家價(jià)值 一個(gè)品牌的鞋子算一個(gè)分組
int max(int a,int b,int c)
{
return a>b?(a>c?a:c):(b>c?b:c);
}
//分組背包問(wèn)題 每組至少取一個(gè)
/*
dp[i][k]是不選擇當(dāng)前鞋子；
dp[i-1][k-v[j]]+w[j]是選擇當(dāng)前鞋子，但是是第一次在本組中選，由于開(kāi)始將該組dp賦為了-1，所以第一次取時(shí)，必須由上一組的結(jié)果推知，這樣才能保證得到全局最優(yōu)解；
dp[i][k-v[j]]+w[j]表示選擇當(dāng)前鞋子，并且不是第一次在本組中取。
*/
/*
這道題dp初始化為-1 因?yàn)槿绻跏蓟癁?
則無(wú)法區(qū)分是買(mǎi)不全那幾款鞋子還是能買(mǎi)全但最大價(jià)值是0
因?yàn)槲覀冊(cè)谫I(mǎi)不全的時(shí)候需要輸出特殊字符。
*/
int main()
{
int n,m,S;
while(scanf("%d%d%d",&n,&m,&S)!=EOF)
{
int i,j,si,vi,ci;
for(i=0;i<n;i++)
{
cin>>si>>ci>>vi;
s[i]=si;
c[i]=ci;
v[i]=vi;
}
for(i=0;i<=S;i++)
{
for(j=0;j<=m;j++)
{
if(i==0)
{
dp[i][j]=0;
}
else
{
dp[i][j]=-1;
}
}
}
for(i=1;i<=S;i++)
{
for(j=0;j<=n;j++)//遍歷所有鞋子
{
if(s[j]==i)//找到品牌為i的鞋子
{
for(int k=m;k>=c[j];k--)//第i組內(nèi)選擇
{
dp[i][k]=max(dp[i][k],dp[i][k-c[j]]+v[j],dp[i-1][k-c[j]]+v[j]);
}
}
}
}
if(dp[S][m]<0)
{
cout<<"Impossible"<<endl;
}
else
{
cout<<dp[S][m]<<endl;
}
}
return 0;
}
