分组背包（c++）

分组背包

有n件物品，被分成k组。每种物品有各自的体积和价值，每件物品都不能拆分。每组中的物品相互冲突，最多只能选取一件。现在给定一个容量为v的背包，如何让背包里装入的物品有最大的价值总和？

输入格式

第一行三个整数n,s和k。
第二行到n+1行都有三个整数，分别表示每组物品的体积，价值和组号。

输出格式

一个整数，表示能够得到的最大价值。

输入输出样例

输入样例

10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3
1
2
3
4
5
6
7

输出样例

20
1

---

此题可以使用一维或二维dp求解。
代码如下：

//模板1：二维dp数组
for(int i=1;i<=m;i++){//对每一组
	for(int j=t;j>=0;j--){//从后往前对每一个剩余空间值
		dp[i][j]=dp[i-1][j];//这组不选物品得到的最大价值
		for(int u=1;u<=g[i][0];u++){
			if(j>=g[i][u])
				dp[i][j]=max(dp[i][j],dp[i][j-g[i][u]]+v[i][u]);//状态转移方程
		}
	}
}
1
2
3
4
5
6
7
8
9
10

//模板2：一维dp数组
for(int i=1;i<=m;i++){//对每一组
	for(int j=t;j>=0;j--){//从后往前对每一个剩余空间值
		//dp[i][j]=dp[i-1][j];//这组不选物品得到的最大价值
		for(int u=1;u<=g[i][0];u++){
			if(j>=g[i][u])
				dp[j]=max(dp[j],dp[j-g[i][u]]+v[i][u]);//状态转移方程
		}
	}
}
1
2
3
4
5
6
7
8
9
10

朋友们，你们有更好的代码吗？请在评论区评论。
好了，这期文章结束了，我们下期再见！