显然状态转移方程为

f[i,j]=max(f[i-1][j],f[i-1,j-v[i,k]]+w[i,k])

其实这个状态转移方程只是粗略的，有很多问题。

依照这个方程粗略地写出代码

#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    int m, n;
    cin >> m >> n; //m=N,n=V

    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 1; k <= s[i] && j >= v[i][k]; k++)
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][k]] + w[i][k]);
    cout << f[m][n] << endl;
    return 0;
}

wa了个痛快！

那么错在哪里呢？

首先让我们写出正确的代码：

#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    int m, n;
    cin >> m >> n; //m=N,n=V

    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 1; k <= s[i]; k++){
                f[i][j] = max(f[i-1][j], f[i][j]);
                if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
            }
    cout << f[m][n] << endl;
    return 0;
}

首先是循环体的K的条件，

for(int k=0;k<=s[i]&&v[i][k]<=j;k++)

这么写有什么问题呢？

v[i] [k]关于k并不是递增的，所以当前的k不满足要求，并不意味着后面的k也不满足要求，不能结束循环，应该改成：

if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);

还有一个小细节！那就是

f[i][j] = max(f[i-1][j], f[i][j]);

因为有可能这一层一个也放不下，但是你不这么写的话那么当前层就为0，而实际应该更新为上一层的值才对。

不得不说压缩成一维才是真的香！！！
我们看一维的

#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    int m, n;
    cin >> m >> n; //m=N,n=V

    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= m; i++)
        for (int j = n; j >= 0; j--)
            for (int k = 1; k <= s[i]; k++){
                //f[i][j] = max(f[i-1][j], f[i][j]);
                if(j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }
    cout << f[n] << endl;
    return 0;
}

注意一下这里注释的地方，删掉了一维就是恒等式了，所以可以省略不写，但写二维的时候一定要写