一、背包問題

有\(n\)件物品和一個(gè)容量為\(m\)的背包。物品\(i\)的體積是\(v_i\)，價(jià)值是\(w_i\)。求解將哪些物品裝入背包可使價(jià)值總和最大

1.01背包問題

01背包問題特點(diǎn)：每種物品僅有一件

狀態(tài)表示：定義\(f(i,j)\)表示只從前\(i\)個(gè)物品中選擇，總體積不超過\(j\)的最大價(jià)值，最終答案為\(f(n,m)\)

狀態(tài)轉(zhuǎn)移：\(f(i,j)\)可以分為不選物品\(i\)和選物品\(i\)兩種情況

狀態(tài)轉(zhuǎn)移方程:

int f[N][N];
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		f[i][j]=f[i-1][j];
		if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
	}
}

優(yōu)化：從二維變成一維

int f[N];
//j從大到小遍歷，保證f[j]在f[j-v[i]]改變前改變，從而使當(dāng)前的f[j-v[i]]表示i-1時(shí)的狀態(tài)
for(int i=1;i<=n;i++)
	for(int j=m;j>=v[i];j++)
		f[j]=max(f[j],f[j-v[i]]+w[i]);

2.完全背包問題

完全背包問題特點(diǎn)：每種物品有無數(shù)件

思路：類比01背包

狀態(tài)表示：定義\(f(i,j)\)表示只從前\(i\)個(gè)物品中選擇，總體積不超過\(j\)的最大價(jià)值

狀態(tài)轉(zhuǎn)移：\(f(i,j)\)可以分為不選物品\(i\)和選\(1\) ~ \(\lfloor\frac{j}{v_i}\rfloor\)個(gè)物品\(i\)兩種情況

等價(jià)變形：\(f(i,j)\)可以分為選\(0\) ~ \(\lfloor\frac{j}{v_i}\rfloor\)個(gè)物品\(i\)的情況

狀態(tài)轉(zhuǎn)移方程:

int f[N][N];
for(int i=1;i<=n;i++)
	for(int j=0;j<=m;j++)
		for(int k=0;k*v[i]<=j;k++)
			f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

優(yōu)化：對(duì)于\(f(i,j)\)和\(f(i,j-v_i)\)而言：

\(f(i,j)=max(f(i-1,j),f(i-1,j-v_i)+w_i,f(i-1,j-2v_i)+2w_i,\cdots)\)

\(f(i,j-v_i)=max(f(i-1,j-v_i),f(i-1,j-2v_i)+w_i,f(i-1,j-3v_i)+2w_i,\cdots)\)

我們驚奇的發(fā)現(xiàn)：\(f(i,j-v_i)\)的表達(dá)式與\(f(i,j)\)的表達(dá)式除第一項(xiàng)以外只差\(w_i\)

于是將狀態(tài)轉(zhuǎn)移方程改寫為：

int f[N][N];
for(int i=1;i<=n;i++)
	for(int j=0;j<=m;j++){
		f[i][j]=f[i-1][j];
		if(j>=w[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
	}

再優(yōu)化：從二維變成一維

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

3.多重背包問題

多重背包問題特點(diǎn)：每種物品有件數(shù)限制

額外定義物品\(i\)有\(s_i\)件

狀態(tài)表示：定義\(f(i,j)\)表示只從前\(i\)個(gè)物品中選擇，總體積不超過\(j\)的最大價(jià)值

狀態(tài)轉(zhuǎn)移：\(f(i,j)\)可以分為選\(0\) ~ \(min(s_i,\lfloor\frac{j}{v_i}\rfloor)\)個(gè)物品\(i\)的情況

狀態(tài)轉(zhuǎn)移方程:

時(shí)間復(fù)雜度：\(O(nms)\)

for(int i=1;i<=n;i++)
	for(int j=0;j<=m;j++)
		for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
			f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

優(yōu)化：轉(zhuǎn)化為01背包問題

假設(shè)物品\(i\)有\(1000\)件，則可以選擇的數(shù)量有\(0,1,2,\cdots,1000\)，我們將物品按\(1,2,4,\cdots,256,489(\)此處為\(1000-511)\)件進(jìn)行“打包”，則可將問題轉(zhuǎn)化為“打包”后新\(\log n\)個(gè)物品的01背包問題，時(shí)間復(fù)雜度 \(O(nms)\)變?yōu)?span id="zlyedxq7" class="math inline">\(O(nm\log s)\)

//這里注意 N 至少要開到 n * logs (基佬紫警告
int v[N],w[N];
int f[N];
int n,m,cnt;
//邊讀邊打包
for(int i=1;i<=n;i++){
	int a,b,s;
	scanf("%d%d%d",&a,&b,&s);
	//打包存儲(chǔ)，cnt記錄打包后物品總數(shù)量 
	int k=1;
	while(k<=s){
		cnt++;
		v[cnt]=a*k;
		w[cnt]=b*k;
		s-=k;
		k*=2;
	}
	//剩余不足 2 的更高次冪個(gè)物品額外打包 
	if(s>0){
		cnt++;
		v[cnt]=a*s;
		w[cnt]=b*s;
	}
} 
//物品個(gè)數(shù)為cnt，背包容量為m的01背包問題模板
for(int i=1;i<=cnt;i++)
	for(int j=m;j>=v[i];j--)
		f[j]=max(f[j],f[j-v[i]]+w[i]);

4.分組背包問題

分組背包問題特點(diǎn)：物品分為多組，每組內(nèi)有若干個(gè)，每組只能選一個(gè)

狀態(tài)表示：定義\(f(i,j)\)表示只從前\(i\)組物品中選擇，總體積不超過\(j\)的最大價(jià)值

狀態(tài)轉(zhuǎn)移：\(f(i,j)\)可以分為不從第\(i\)組物品中選和從第\(i\)組物品中選第\(k\)個(gè)物品兩種情況

狀態(tài)轉(zhuǎn)移方程：

優(yōu)化：從二維變成一維（類比01背包，\(j\)從大到小遍歷）

int n,m;//n組物品，容量為m
int v[N][N],w[N][N],s[N];//s[i]表示第i組物品的件數(shù)
int f[N];
for(int i=1;i<=n;i++)
	for(int j=m;j>=0;j--)
		for(int k=1;k<=s[i];k++)
			if(v[i][k]<=j)
				f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);