分组背包¶
问题描述¶
所给的物品被划分为若干组,同一组的物品互相冲突,最多选一件
比如你去旅游要带手机(组),你只能从你的一堆手机中挑一个带上(不同手机间互斥)
方法¶
分组 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]);