分组背包¶
问题描述¶
所给的物品被划分为若干组，同一组的物品互相冲突，最多选一件
比如你去旅游要带手机（组），你只能从你的一堆手机中挑一个带上（不同手机间互斥）
方法¶
分组 0-1 背包¶
先上例题：「Luogu P1757」通天之分组背包
决策：对于每一组，要么从这一组选 一个，要么不选
容易得到状态转移方程如下：
f[k][j]=max(f[k-1][j],f[k-1][j-w[i]]+v[i]) 其中 i 属于第 k 组
同样使用滚动数组优化掉一维，压缩至一维，得到：
f[j]=max(f[j],f[j-w[i]]+v[i]) 其中 i 属于第 k 组
考虑枚举顺序，要保证 f[j] 先于 f[j-w[i]] 更新，故应逆序枚举 j
代码如下：
for(int k=1;k<=n;k++)
for(int j=W;j>=0;j--)
for(int i=0;i<cnt[j];i++)
f[j]=max(f[j],f[j-w[i]]+v[i]);