分组背包问题

思想

[i,k]表示选第i组的第k个

枚举从大到小还是从小到大？
如果要用到上一层的状态的话，就要从大到小，反之从小到大

关键是用二维数组表示，其余和01背包差别不大

代码：

#include 
using namespace std;
const int MAXN = 1010;
int w[MAXN][MAXN],v[MAXN][MAXN],dp[MAXN],s[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,i,j,k;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        {
            cin>>s[i];
            for(k=0;k<s[i];k++)
            {
                cin>>v[i][k]>>w[i][k];
            }
        }
    for(i=1;i<=n;i++)
        for(j=m;j>=0;j--)
            for(k=0;k<s[i];k++)
    {
        if(v[i][k]<=j)
            dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
    }
        cout<<dp[m];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28