[笔记]分组背包

P1757 通天之分组背包

分组背包模板题

总共 $s$ 组，每组最多取一个物品，实际上就是一个物品总数为 $s$ 的背包。

for(int i=1;i<=s;i++){//枚举组
	for(int j=1;j<=n[i];j++){//枚举每组的元素
		for(int k=1;k<=m;k++){//枚举背包大小
			f[i][k]=max(f[i][k],f[i-1][k]);
			if(k>=w[i][j])
				f[i][k]=max(f[i][k],f[i-1][k-w[i][j]]+v[i][j]);
		}
	}
}

仔细观察，可以发现代码和 01 背包十分相似，只不过外面套了一个枚举组的循环。

但是还有一点和 01 背包有区别，就是第 $4$ 行，还需要和自己比较一次，这是因为我们之前枚举同组的其他元素时，可能已经给 $f[i][k]$ 赋值了，所以不能忽略，需要参与比较。

接下来我们考虑如何优化空间。

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

与上面的代码相比，我们修改了两个部分：

• $k$ 改为从大到小。 这是为了让 $f[k-w[i][j]]$ 求到的是上一层的、未修改过的值，与 01 背包的空间优化相似。
• 将枚举 $j,k$ 的循环反转位置。 我们发现，如果把 $k$ 放在最内层的话， $j$ 每增加 $1$ ， $f$ 的内容就要翻新一遍，这样我们求的 $f[k-w[i][j]]$ 就已经修改过了，并不是上一层的原值了，所以我们把 $j$ 放在最里面。

时间复杂度 $O({\sum }_{i=1}^{s}n[i]\ast m)$ 。 空间复杂度 $O(m)$ 。

---

下面放上完整代码：

优化前 Code

#include<bits/stdc++.h>
using namespace std;
int n[110],m,t,s;
int w[110][1010],v[110][1010];
int f[110][1010];
int main(){
	cin>>m>>t;
	for(int i=1;i<=t;i++){
		int a,b,c;
		cin>>a>>b>>c;
		n[c]++;
		w[c][n[c]]=a;
		v[c][n[c]]=b;
		s=max(s,c);
	}
	for(int i=1;i<=s;i++){
		for(int j=1;j<=n[i];j++){
			for(int k=1;k<=m;k++){
				f[i][k]=max(f[i][k],f[i-1][k]);
				if(k>=w[i][j])
					f[i][k]=max(f[i][k],f[i-1][k-w[i][j]]+v[i][j]);
			}
		}
	}
	cout<<f[s][m];
	return 0;
}

优化后 Code

#include<bits/stdc++.h>
using namespace std;
int n[110],m,t,s;
int w[110][1010],v[110][1010];
int f[1010];
int main(){
	cin>>m>>t;
	for(int i=1;i<=t;i++){
		int a,b,c;
		cin>>a>>b>>c;
		n[c]++;
		w[c][n[c]]=a;
		v[c][n[c]]=b;
		s=max(s,c);
	}
	for(int i=1;i<=s;i++){
		for(int k=m;k>=1;k--){
			for(int j=1;j<=n[i];j++){
				if(k>=w[i][j]) f[k]=max(f[k],f[k-w[i][j]]+v[i][j]);
			}
		}
	}
	cout<<f[m];
	return 0;
}

树上 DP + 分组背包

树形 DP + 分组背包解法思路：

• $f[u][i]$ 表示以 $u$ 为根的子树中，容量为 $i$ 时的最大价值
• 对于每个子树，将其看作一个物品组，使用分组背包的思路合并

伪代码：

void dfs(int u) {
	f[u][0] = 0; // 初始化容量为0时的价值为0
	for (auto v : children[u]) { // 遍历子节点
		dfs(v);
		for (int j = m; j >= 0; j--) { // 从大到小遍历容量
			for (int k = 0; k <= j; k++) { // 遍历子节点的容量分配
					f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
			}
		}
	}
}