只能选择每一组中的一个物品

模板

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i ++)
    {
        scanf ("%d", &s[i]);
        for (int j = 1; j <= s[i]; j ++)
            scanf ("%d %d", &v[i][j], &w[i][j]);
    }

    for (int i = 1; i <= n; i ++)
        for (int j = m; j >= 0; j --) // 每组里只能选一个
            for (int k = 1; k <= s[i]; k ++) // 枚举每一个组里的物品
                if (v[i][k] <= j) // 如果这个体积小于等于j才能继续算
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    printf ("%d", f[m]);
    return 0;
}

金明的预算方案

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define v first
#define w second

typedef pair<int, int> PII;

const int N = 60, M = 32000;

int n, m;
PII master[N];
vector<PII> servent[N];
int f[M];

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

    for (int i = 1; i <= n; i ++)
    {
        int v, w, q;
        cin >> v >> w >> q;
        if (!q) master[i] = {v, v * w};
        else servent[q].push_back({v, v * w});
    }

    for (int i = 1; i <= n; i ++)
        if (master[i].v)
        {
            for (int j = m; j >= 0; j --)
            {
                auto &sv = servent[i];
                for (int k = 0; k < 1 << sv.size(); k ++) // 运用二进制的每一位上是否为1表示是否选这个物件
                {
                    int v = master[i].v, w = master[i].w; // 先要把主件的体积和价值加上
                    for (int u = 0; u < sv.size(); u ++)
                        if (k >> u & 1)
                        {
                            v += sv[u].v;
                            w += sv[u].w;
                        }
                    if (j >= v) f[j] = max(f[j], f[j - v] + w); // 一定要记得j >= v这个条件
                }
            }
        }

    cout << f[m];
    return 0;
}