思路一：
直接记忆化搜索（遇见不会的 dp 先记忆化搜索了再说（记忆化过不了就是需要优化））

#include <bits stdc++.h>

using namespace std;

int n, m;
vector<pii> ve[69];

int dp[100][42009], vis[100][42009];

int dfs(int x, int s) {
    if(s &lt; 0) return intmax + 1;
    if(x &gt; m) return 0;
    if(vis[x][s] ++) return dp[x][s];  /// 防止进入后续递归过程
    if(ve[x].size() == 0) return dp[x][s] = dfs(x + 1, s);
    int ans = max(dfs(x + 1, s), dfs(x + 1, s - ve[x][0].first) + ve[x][0].second);  /// 不取  /// 取一个
    if(ve[x].size() &gt; 1)
        ans = max(ans, dfs(x + 1, s - ve[x][0].first - ve[x][1].first) + ve[x][0].second + ve[x][1].second);  /// 取两个       
    if(ve[x].size() &gt; 2) {
        ans = max(ans, dfs(x + 1, s - ve[x][0].first - ve[x][2].first) + ve[x][0].second + ve[x][2].second);  /// 取两个
        ans = max(ans, dfs(x + 1, s - ve[x][0].first - ve[x][1].first - ve[x][2].first)
                   + ve[x][0].second + ve[x][1].second + ve[x][2].second);    /// 取三个
    }
    return dp[x][s] = ans;
}
int main() {
    cin &gt;&gt; n &gt;&gt; m;
    int x, y, z;
    for(int i = 1; i &lt;= m; i ++) {
        cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;
        if(z) ve[z].push_back({x, y * x});
        else ve[i].push_back({x, y * x});
    }
    cout &lt;&lt; dfs(1, n);
    return 0;
}

思路二：
此题非常像 01背包 问题，只是由于附件必须依赖于主件所有使得问题麻烦了起来

  • 对于不同类物品之间不存在依赖关系，故可以直接用 01背包 的方式 dp
  • 对于同类物品之间，我们使用 附件+主件 的格式将物品组合在一起考虑
    • 那么我们只能在这一类物品之间选择一个，这个子问题可以通过 dp 解决（分类进行 01背包 递推后对于同一类物品使用相同的递推方程，转移过程来源与之前同类物品的来源相似（不要忘记对自己也要进行一个判断）） 
#include <bits stdc++.h>

using namespace std;

const int N = 32009, M = 69;

int n, m;
vector<pii> ve[M];

int dp[M][N];

int main() {
    cin &gt;&gt; n &gt;&gt; m;
    int v, w, q;
    for(int i = 1; i &lt;= m; i ++) {
        cin &gt;&gt; v &gt;&gt; w &gt;&gt; q;  w *= v;
        if(q) {
            int x = ve[q].size();
            for(int j = 0; j &lt; x; j ++) {  /// 状态转移（构造最多四种选择状态）
                ve[q].push_back({v + ve[q][j].first, w + ve[q][j].second});
            }
        } else ve[i].push_back({v, w});
    }
    for(int i = 1; i &lt;= m; i ++)   /// 注意，由于上面的转移，这条语句必须位于读入的后方
        ve[i].push_back({0, 0});   /// 保证连续性（存在“不取”这种取法）
    for(int i = m; i; i --) {   /// 枚举类
        int q = ve[i].size();
        for(int j = 0; j &lt; q; j ++) {   /// 枚举同类中物品
            v = ve[i][j].first, w = ve[i][j].second;
            for(int k = n; k &gt;= v; k --) {   /// 枚举空间
                dp[i][k] = max(dp[i][k], max(dp[i + 1][k - v] + w, dp[i + 1][k]));
            }
        }
    }
    cout &lt;&lt; dp[1][n];
    return 0;
}

思考：

  • 我们学习算法总是会选择“最优解”来“记忆“（有时甚至是背诵），但是这题正是基于没有空间优化的 01背包 进行的推导（当然上述代码还可以进行空间优化），但是 左神 告诉我们：每个算法都是一步一步慢慢来的！