动态规划01背包问题

声明：对xiaowei_cqu大佬的博客 算法设计_背包问题 的学习记录以及部分延申，欢迎讨论

完全背包

目标函数 $max\sum_{j=1}^{n}v_jx_j$max∑j=1n​vj​xj​ $v_j$vj​表示第j件物品的价值 $x_j$xj​表示第j件物品的数量

约束条件 $\sum_{j=1}^{n}w_jx_j<=b$∑j=1n​wj​xj​<=b $w_j$wj​表示第j件物品的重量

设$F_k(y)$Fk​(y) 表示只允许装前k 种物品,背包总重不超过y 时背包的最大价值。

$F_k(y)$Fk​(y) 有两种情况：不装第k种物品或至少装1件第k种物品。
①不装第k种物品，那么只能用前k-1种物品装入背包，背包的限制重量仍为y，所以最大价值是$F_{k-1}(y)$Fk−1​(y)；
②装1件第k种物品，那么装入的第k种物品价值为$v_k$vk​，重量为$w_k$wk​，剩下的物品仍要在前k种里选择。于是问题规约为背包限制重量$y-w_k$y−wk​的情况下前k种物品取得最大价值，即$F_k(y-w_k)+v_k$Fk​(y−wk​)+vk​。

递推方程：
$F_k(y)=max(F_{k-1}(y),F_k(y-w_k)+v_k)$Fk​(y)=max(Fk−1​(y),Fk​(y−wk​)+vk​)

标记函数：
$i_k(y)=\begin{cases}i_{k-1}(y)\quad\quad F_{k-1}(y)>F_k(y-w_k)+v_k\\k\quad\quad\quad\quad F_{k-1}(y)<=F_k(y-w_k)+v_k\end{cases}$ik​(y)={ik−1​(y)Fk−1​(y)>Fk​(y−wk​)+vk​kFk−1​(y)<=Fk​(y−wk​)+vk​​

void dpbag(int v[N],int w[N],int F[][B+1],int tagi[][B+1]){
	for(int k=0;k<=N;k++){
		F[k][0]=0;//前k种物品总重不超过0时价值
		tagi[k][0]=0;//前k种物品总重不超过0时标记
	}
	for(int y=0;y<=B;y++){
		F[0][y]=0;
		F[1][y]=(int)(y/w[0])*v[0];//只装第一种物品时价值
		tagi[0][y]=0;
	}
 
	for(int k=1;k<=N;k++){
		for(int y=1;y<=B;y++){
			if(y-w[k-1]<0){
				F[k][y]=F[k-1][y];
				tagi[k][y]=tagi[k-1][y]; 
			}
			else{
				//允许装入k种物品，价值的两种情况：
				//不装第k种物品或至少装1件第k种物品
				F[k][y]=F[k-1][y]>F[k][y-w[k-1]]+v[k-1] ? F[k-1][y]:(F[k][y-w[k-1]]+v[k-1]);
				tagi[k][y]=F[k-1][y]>F[k][y-w[k-1]]+v[k-1]?tagi[k-1][y]:k;
			}
		}
	}
}

---

$w_0=2,w_1=4,w_2=5,w_3=5,w_4=6.$w0​=2,w1​=4,w2​=5,w3​=5,w4​=6.

$v_0=1,v_1=2,v_2=4,v_3=3,v_4=6.$v0​=1,v1​=2,v2​=4,v3​=3,v4​=6.

$F_k(y)$Fk​(y)

k\Y	1	2	3	4	5	6	7	8	9	10
1	0	1	1	2	2	3	3	4	4	5
2	0	1	1	2	2	3	3	4	4	5
3	0	1	1	2	4	4	5	5	6	8
4	0	1	1	2	4	4	5	5	6	8
5	0	1	1	2	4	6	6	7	7	8

$i_k(y)$ik​(y)

k\y	1	2	3	4	5	6	7	8	9	10
1	0	1	1	1	1	1	1	1	1	1
2	0	1	1	2	2	2	2	2	2	2
3	0	1	1	2	3	3	3	3	3	3
4	0	1	1	2	3	3	3	3	3	3
5	0	1	1	2	3	5	5	5	5	5

---

void TrackSolution(int v[N],int w[N],int tagi[][B+1]){
	//x[i-1]标记第i种物品的件数
	int x[N];
	for(int i=0;i<N;i++)
		x[i]=0;
	int y=B,j=tagi[N][B];
	while (tagi[j][y]!=0){
		 j=tagi[j][y];
		//标记函数尾ik(y)标记的物品取一件
		x[j-1]=1; 
		y=y-w[j-1];
		while (tagi[j][y]==j){
			y=y-w[j];
			x[j-1]=x[j-1]+1;
		}
	}
}

计算选取方案

观察标记函数右下角开始

$i_5(10)=5$i5​(10)=5

第5种物品确定选取（先按1件处理） 继续背包剩余重量$10-w_4$10−w4​

$i_5(10-w_4)=i_5(4)=2$i5​(10−w4​)=i5​(4)=2

第2种物品确定选取 (先按1件处理) 并确定上一步第5种物品只选了1件 继续背包剩余重量$4-w_1$4−w1​

$i_5(4-w_1)=i_5(0)=0$i5​(4−w1​)=i5​(0)=0

确定上一步第2种物品只选了1件 结束

总终选取情况应为 01001

运行结果

---

---

背包问题变种:硬币找零问题

目标函数 $min\sum_{j=1}^nw_jx_j$min∑j=1n​wj​xj​

约束条件 $\sum_{j=1}^nv_jx_j=V$∑j=1n​vj​xj​=V

设$F_k(y)$Fk​(y) 表示只允许装前k 种硬币,硬币总价值等于y 时包的最小重量。

$F_k(y)$Fk​(y) 有两种情况：不装第k种硬币或至少装1件第k种硬币。
①不装第k种硬币，那么只能用前k-1种硬币装入包，包的限制价值仍为y，所以最小重量是$F_{k-1}(y)$Fk−1​(y)；
②装1枚第k种硬币，那么装入的第k种硬币价值为$v_k$vk​，重量为$w_k$wk​，剩下的硬币仍要在前k种里选择。于是问题规约为包限制价值$y-v_k$y−vk​的情况下前k种硬币取得最小重量，即$F_k(y-v_k)+w_k$Fk​(y−vk​)+wk​。

递推方程：$F_k(y)=min(F_{k-1}(y),F_k(y-v_k)+w_k)$Fk​(y)=min(Fk−1​(y),Fk​(y−vk​)+wk​)

标记函数：$i_k(y)=\begin{cases}i_{k-1}(y)\quad\quad F_{k-1}(y)<F_k(y-v_k)+w_k\\k\quad\quad\quad\quad F_{k-1}(y)>=F_k(y-v_k)+w_k\end{cases}$ik​(y)={ik−1​(y)Fk−1​(y)<Fk​(y−vk​)+wk​kFk−1​(y)>=Fk​(y−vk​)+wk​​

void dpbag(int v[N],int w[N],int F[][V+1],int tagi[][V+1]){
	for(int k=0;k<=N;k++){
		F[k][0]=0;//前k种硬币总价值不超过0时重量
		tagi[k][0]=0;//前k种硬币总价值不超过0时标记
	}
	for(int y=0;y<=V;y++){
		F[0][y]=0;
		F[1][y]=y*w[0];//只装第一种硬币时重量
		tagi[1][y]=1;
	}
 
	for(int k=1;k<=N;k++){
		for(int y=1;y<=V;y++){
            
			if(y-v[k-1]<0){
				F[k][y]=F[k-1][y];
				tagi[k][y]=tagi[k-1][y]; 
			}
			else{
				//允许装入k种硬币，重量的两种情况：
				//不装第k种硬币或至少装1枚第k种硬币
				F[k][y]=F[k-1][y]>F[k][y-v[k-1]]+w[k-1] ? (F[k][y-v[k-1]]+w[k-1]):F[k-1][y];
				tagi[k][y]=F[k-1][y]>F[k][y-v[k-1]]+w[k-1]?k:tagi[k-1][y];
			}
		}
	}
}

---

$w_0=1,w_1=2,w_2=4,w_3=6.$w0​=1,w1​=2,w2​=4,w3​=6.

$v_0=1,v_1=4,v_2=6,v_3=8.$v0​=1,v1​=4,v2​=6,v3​=8.

$F_k(y)$Fk​(y)

k\Y	1	2	3	4	5	6	7	8	9	10	11	12
1	1	2	3	4	5	6	7	8	9	10	11	12
2	1	2	3	2	3	4	5	4	5	6	7	6
3	1	2	3	2	3	4	5	4	5	6	7	6
4	1	2	3	2	3	4	5	4	5	6	7	6

$i_k(y)$ik​(y)

k\y	1	2	3	4	5	6	7	8	9	10	11	12
1	1	1	1	1	1	1	1	1	1	1	1	1
2	1	1	1	2	2	2	2	2	2	2	2	2
3	1	1	1	2	2	3	3	2	2	3	3	2
4	1	1	1	2	2	3	3	2	2	3	3	2

---

void TrackSolution(int v[N], int w[N], int tagi[][V + 1]) {
	//x[i-1]标记第i种硬币的枚数
	int x[N];
	for (int i = 0; i < N; i++)
		x[i] = 0;
	int y = V, j = tagi[N][V];
	while (tagi[j][y] != 0) {
		j = tagi[j][y];
		//标记函数最下角ik(y)标记的硬币取一枚
		x[j - 1] = 1;
		y = y - v[j - 1];
		while (tagi[j][y] == j) {
			y = y - v[j-1];
			x[j - 1] = x[j - 1] + 1;
		}
	}
	printf_s("硬币数量：\n");
	for (int k = 0; k < N; k++)
	{
		printf_s(" %d", x[k]);
	}
}

计算选取方案

观察标记函数右下角开始

$i_4(12)=2$i4​(12)=2

第2种硬币确定选取（先按1枚处理） 继续总额剩余价值$12-v_2$12−v2​

$i_2(12-v_2)=i_2(8)=2$i2​(12−v2​)=i2​(8)=2

第2种物品确定选取 (先按2件处理) 继续总额剩余价值$8-v_2$8−v2​

$i_2(8-v_2)=i_2(4)=2$i2​(8−v2​)=i2​(4)=2

第2种物品确定选取 (先按3件处理) 继续总额剩余价值$4-v_2$4−v2​

$i_2(4-v_2)=i_2(0)=0$i2​(4−v2​)=i2​(0)=0

确定上一步第2种物品只选了3件 结束

总终选取情况应为 0300

运行结果

---