分组背包问题，转化为0-1背包问题

看了各个大佬的分析，终于写出了我自己的代码，其实知道了如何进行状态转移，就基本大差不差

#include <bits/stdc++.h>

using namespace std;

int main()
{
    // 带条件的0-1背包问题
    // 创建dp数组
    int N(0), m(0);
    cin >> N >> m;
    // N是总预算，相当于背包问题的容量
    int tv(0), tp(0), tq(0);
    //vector<vector<int>> dp(m+1, vector<int>(N/10+1, 0));
    vector<vector<int>> primary;
    map<int, vector<vector<int>>> sub;
    map<int, int> linenumtomainnum;
    int i=0;
    while (i<m) {
        cin >> tv >> tp >> tq;
        if (tq == 0)
        {
            primary.push_back(vector<int>{tv, tp, tq});
            linenumtomainnum[i+1] = primary.size() - 1;
        }
        else {
            sub[linenumtomainnum[tq]].push_back(vector<int>{tv, tp, tq});
        }
        i++;
    }
    // 有mainnum个主件
    // 初始化
    vector<vector<int>> w(primary.size(), vector<int>{});
    vector<vector<int>> v(primary.size(), vector<int>{});
    for (int i = 0; i<primary.size(); i++) {
        int subsize = sub[i].size();    // 附件的数量
        int wp = primary[i][0];
        int vp = primary[i][0] * primary[i][1];        // 主件的w(价格)和v(价格乘重要程度)
                                                       // 加入只有主件的情况
        w[i].push_back(wp);
        v[i].push_back(vp);
        if (subsize == 0)    // 如果没有继续向下，说明存在至少一个附件
            continue;
        if (subsize == 1)    // 只有一个附件
        {
            int ws1 = sub[i][0][0];    // 附件的价格
            int vs1 = sub[i][0][0] * sub[i][0][1];    // 附件的价格乘重要程度
                                                      // 主件+附件的模式
            w[i].push_back(ws1 + wp);
            v[i].push_back(vs1 + vp);
        }
        if (subsize == 2)    // 有两个附件,附件1+附件2
        {
            int ws1 = sub[i][0][0];    // 附件的价格
            int vs1 = sub[i][0][0] * sub[i][0][1];    // 附件的价格乘重要程度
            int ws2 = sub[i][1][0];    // 附件的价格
            int vs2 = sub[i][1][0] * sub[i][1][1];    // 附件的价格乘重要程度
                                                      // 主件+附件1
            w[i].push_back(wp + ws1);
            v[i].push_back(vp + vs1);
            // 主件+附件2
            w[i].push_back(wp + ws2);
            v[i].push_back(vp + vs2);
            // 主件+附件1+附件2
            w[i].push_back(wp + ws1 + ws2);
            v[i].push_back(vp + vs1 + vs2);
        }
    }
    // 动态规划开始
    vector<vector<int>> dp(w.size() + 1, vector<int>(N / 10 + 2, 0));
    for (int i = 1; i <= w.size(); i++) {
        int ti = i - 1;
        for (int j = 0; j <= N+10; j += 10) {
            int tj = j / 10;
            dp[i][tj] = dp[i - 1][tj];
            for (int k = 0; k<w[ti].size(); k++) {
                if(j>=w[ti][k])
                    dp[i][tj] = max(dp[i][tj], dp[i - 1][(j-w[ti][k])/10] + v[ti][k]);
            }
        }
    }
    cout << dp[w.size()][N/10+1] << endl;
    return 0;
}

不过我的代码没有经过优化，应该能用一维数组来做的，不过先不管了，菜鸡如我还是先学习背包问题的套路吧，优化后面再说