分组背包

因为每组至多选择一个物品，可以将每组看做一个整体，这样就类似于01背包问题。

用\(f(i,j)\)表示前\(i\)组物品放入一个容量不超过\(j\)的背包可以获得的最大价值。

对于第\(i\)组物品：

• 不放入第\(i\)组物品，\(f(i,j)\)=\(f(i-1,j)\)
• 放入第\(i\)组的第\(k\)个物品，\(f(i,j)\)=\(max(f(i-1,j-v_{ik})+w_{ik})\)，\(1<=k<=s_i\)

const int N=110;
int f[N];
int v[N],w[N];
int n,m;

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        int s;
        cin>>s;
        for(int j=1;j<=s;j++) cin>>v[j]>>w[j];

        for(int j=m;j>=0;j--)
            for(int k=1;k<=s;k++)
                if(j>=v[k])
                    f[j]=max(f[j],f[j-v[k]]+w[k]);
    }

    cout<<f[m]<<endl;
    
    //system("pause");
}