分组背包

物品种类分组，每组有不同种类的物品，每个组只能选一种

• 水果
  • 苹果
  • 香蕉
• 蔬菜
  • 土豆
  • 香菜

一样的，dp[i][j] 表示前 i 组，背包空间 j，还是会分为这组我选不选？我选了的话选组里的哪个？

朴素版本就是 dp[i][j] = max(dp[i-1][j], ... , dp[i-1][j-v[i][k]]+w[i][k], ... )

参考 多重背包，组里的哪个可以通过二进制表示，

朴素

直接写一维的朴素

for(int i = 1; i <= n; ++i) {
	for(int j = m; j >= 0; --j) {  // 因为二维情况要的是前一层
		for(int k = 1; k <= s[i]; ++k) {
			if(j >= v[i][k]) dp[j] = max(dp[j], dp[j-v[i][k]]+w[i][k]);
		}
	}
}

(⬆️ 我自己尝试写的，没问题)

ok 啊，最后没有优化了，分组背包就只有这样了