题解 P1757 【通天之分组背包】

· · 题解

正如题目名所说，这是一道 分组背包

使用一维数组的伪代码如下：

for 所有的组k
    for v=V..0
        for 所有的i属于组k
　　　　　　f[v]=max{f[v],f[v-w[i]]+c[i]}

注意这里的三层循环的顺序，“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。

#include <bits/stdc++.h>//万能库
using namespace std;
const int M=1010,N=1010;
int n,m;
int f[M],a[N],b[N],c[101][20],cc[101],cn;
int main() 
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        int C;
        scanf("%d%d%d",&a[i],&b[i],&C);
        cn=max(cn,C);//cn记录共有几组
        cc[C]++;//cc[]记录第C组共有几件物品
        c[C][cc[C]]=i;//c[][]记录第C组第i件物品的的序号
    }
    for(int i=1;i<=cn;i++)//枚举cn个组
        for(int j=m;j>=0;j--)//枚举容量
            for(int k=1;k<=cc[i];k++)//枚举各组中物品的序号
            if(j>=a[c[i][k]])
            f[j]=max(f[j],f[j-a[c[i][k]]]+b[c[i][k]]);//套用状态转移方程
    printf("%d\n",f[m])；//CE
}