题目的主要信息：

• 输入一个$NN$N和一个$mm$m，$NN$N表示现有的钱，$mm$m表示有$mm$m件物品，接着输入每件物品的价格、重要度、是否附属等信息
• 对于主件物品可以直接买，对于附件物品需要先购买主件才能购买附件，主件有0-2个附件
• 所有的价格，及金额都是10的整数倍
• 在不超过金额$NN$N元的情况下，使购买的每件物品的价格与重要度乘积的和最大，求这个最大值

方法一：动态规划

具体做法：

因为每个主件只有0-2个附件，且附件必须在买了主件的前提下，才能买，因此我们可以用$3\ast m3*m$3∗m的数组保存价格和重要度与价格的乘积，第一维就是主件，第二三维是主件后面跟的附件，只有主件下标的元素才有值，附件下标的数组元素就都是0。且因为金钱和价格都是10的整数倍，我们可以对其除10，缩小使用的时间和空间。

然后我们用动态规划来解决这个问题，设$dp\left[i\right]\left[j\right]dp[i][j]$dp[i][j]表示遍历了$ii$i个主件物品及其附件，我们有$jj$j元钱最多能买多少乘积和，容易看出来$dp\left[m\right]\left[N\right]dp[m][N]$dp[m][N]就是我们要求的答案。

初始状态：0件物品，或是0元，那肯定都是0； 转移的过程中，我们优先考虑遍历的主件物品，如果当前$jj$j大于等于这个主件物品的价格，我们可以考虑加入买它或者不买他，分别计算买或者不买的最大值，如果要买的需要前一次还剩余$j-pricej-price$j−price的钱才能买，于是我们有：

$dp\left[i\right]\left[j\right]=max\left(dp\right[i-1\left]\right[j],dp[i-1\left]\right[j-price\left[i\right]\left[0\right]]+multisum[i\left]\right[0\left]\right)dp[i][j]=max(dp[i-1][j],\; dp[i-1][j-price[i][0]]+multisum[i][0])$dp[i][j]=max(dp[i−1][j],dp[i−1][j−price[i][0]]+multisum[i][0])，遍历所有的$ii$i和$jj$j将dp数组填满就行了，这是最基础的01背包问题。

但是这题不一样，这题还要考虑附件，因此我们后续还要考虑$jj$j是否足够买这个下标下的主件加第一个附件，这个下标下的主件加第二个附件，这个下标下的主件加两个附件三种请况，每次都是寻找上一轮剩余的钱足够买的乘积和加上这一轮得到的乘积和，取最大值就可以了。公式类似上面主件部分。比如主件+第一个附件的公式：

$dp\left[i\right]\left[j\right]=max\left(dp\right[i-1\left]\right[j-price\left[i\right]\left[0\right]-price\left[i\right]\left[1\right]]+multisum[i\left]\right[0]+multisum[i\left]\right[1],dp[i\left]\right[j\left]\right)dp[i][j]\; =\; max(dp[i-1][j\; -\; price[i][0]\; -\; price[i][1]]\; +\; multisum[i][0]\; +\; multisum[i][1],\; dp[i][j])$dp[i][j]=max(dp[i−1][j−price[i][0]−price[i][1]]+multisum[i][0]+multisum[i][1],dp[i][j])

遍历dp数组，填满得到$dp\left[m\right]\left[N\right]dp[m][N]$dp[m][N]就可以了。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
    int N, m;
    cin >> N >> m;
    N /= 10; //所有价格及金钱都是10倍数
    vector<vector<int> > price(m + 1, vector<int>(3, 0)); //记录价格及附件价格
    vector<vector<int> > multi_sum(m + 1, vector<int>(3, 0)); //记录重要度*价格
    vector<vector<int> > dp(m + 1, vector<int>(N + 1, 0)); //dp数组
    for(int i = 1; i <= m; i++){ //遍历输入，将所有价格及乘积信息录入数组
        int v, p, q;
        cin >> v >> p >> q; //输入价格、重要度、附属信息
        v /= 10;   //所有价格及金钱都是10倍数
        p *= v;  //重要度乘上价格
        if(q == 0){ //主件
            price[i][0] = v;
            multi_sum[i][0] = p;
        }else{ //附件
            if(price[q][1] == 0){ //第一个附件
                price[q][1] = v;
                multi_sum[q][1] = p;
            }else{ //第二个附件
                price[q][2] = v;
                multi_sum[q][2] = p;
            }
        }
    }
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= N; j++){
            if(j >= price[i][0]) //可以买这个的主件
                dp[i][j] = max(dp[i - 1][j - price[i][0]] + multi_sum[i][0], dp[i - 1][j]); //选择买这个与不买这个的最大值
            else
                dp[i][j] = dp[i - 1][j];
            if(j >= price[i][0] + price[i][1]) //可以买主件 + 第一个附件
                dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][1]] + multi_sum[i][0] + multi_sum[i][1], dp[i][j]);
            if(j >= price[i][0] + price[i][2]) //可以买主件 + 第二个附件
                dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][2]] + multi_sum[i][0] + multi_sum[i][2], dp[i][j]);
            if(j >= price[i][0] + price[i][1] + price[i][2]) //可以买主件 + 两个附件
                dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][1] - price[i][2]] + multi_sum[i][0] + multi_sum[i][1] + multi_sum[i][2], dp[i][j]);
        }
    }
    cout << dp[m][N] * 10 << endl;  //输出要乘回10倍
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(mn\right)O(mn)$O(mn)，其中$n=N/10n=N/10$n=N/10，遍历dp数组，两层循环
• 空间复杂度：$O\left(mn\right)O(mn)$O(mn)，dp数组的空间大小

方法二：空间记忆递归

具体做法：

上面的动态规划也可以化为递归。动态规划从第一个元素开始相加，递归则从最后一个元素开始考虑，要或者不要，分别往前得到最开始的值，然后又加回到最后。但是这样的话，每到一个物品都要递归回到最初的0，很浪费时间，我们可以用dp数组记录递归过程中算出来的中间结果，后续就不用再多次重复计算了。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int recursion(int m, int N, vector<vector<int>>& price, vector<vector<int>>& multi_sum, vector<vector<int>>& dp){
    if(m == 0 || N == 0)
        return dp[m][N] = 0;
    else if(price[m][0] > N){ //买不了该主件，进入下一个
        if(dp[m - 1][N] == -1)
            dp[m - 1][N] = recursion(m - 1, N, price, multi_sum, dp);
        return dp[m - 1][N];
    }
    else{ //可以装下主件的情况
        if(dp[m - 1][N] == -1)
            dp[m - 1][N] = recursion(m - 1, N, price, multi_sum, dp); //不装
        if(dp[m - 1][N - price[m][0]] == -1)
            dp[m - 1][N - price[m][0]] = recursion(m - 1, N - price[m][0], price, multi_sum, dp); //装
        dp[m][N] = max(dp[m - 1][N], dp[m - 1][N - price[m][0]] + multi_sum[m][0]);  //对于第m项主件的情况
        if(N >= price[m][0] + price[m][1]){//买得起主件+第一个附件
            if(dp[m - 1][N - price[m][0] - price[m][1]] == -1)
                dp[m - 1][N - price[m][0] - price[m][1]] = recursion(m - 1, N - price[m][0] - price[m][1], price, multi_sum, dp);
            dp[m][N] = max(dp[m][N], dp[m - 1][N - price[m][0] - price[m][1]] + multi_sum[m][0] + multi_sum[m][1]);
        }
        if(N >= price[m][0] + price[m][2]){//买得起主件+第2个附件
            if(dp[m - 1][N - price[m][0] - price[m][2]] == -1)
                dp[m - 1][N - price[m][0] - price[m][2]] = recursion(m - 1, N - price[m][0] - price[m][2], price, multi_sum, dp);
            dp[m][N] = max(dp[m][N], dp[m - 1][N - price[m][0] - price[m][2]] + multi_sum[m][0] + multi_sum[m][2]);
        }
        if(N >= price[m][0] + price[m][1] + price[m][2]){//买得起主件+两个附件
            if(dp[m - 1][N - price[m][0] - price[m][1] - price[m][2]] == -1)
                dp[m - 1][N - price[m][0] - price[m][1] - price[m][2]] = recursion(m - 1, N - price[m][0] - price[m][1] - price[m][2], price, multi_sum, dp);
            dp[m][N] = max(dp[m][N], dp[m - 1][N - price[m][0] - price[m][1] - price[m][2]] + multi_sum[m][0] + multi_sum[m][1] + multi_sum[m][2]);
        }
        return dp[m][N];
    }
    return 0;
}

int main(){
    int N, m;
    cin >> N >> m;
    N /= 10; //所有价格及金钱都是10倍数
    vector<vector<int> > price(m + 1, vector<int>(3, 0)); //记录价格及附件价格
    vector<vector<int> > multi_sum(m + 1, vector<int>(3, 0)); //记录重要度*价格
    vector<vector<int> > dp(m + 1, vector<int>(N + 1, -1)); //dp数组
    for(int i = 1; i <= m; i++){ //遍历输入，将所有价格及乘积信息录入数组
        int v, p, q;
        cin >> v >> p >> q; //输入价格、重要度、附属信息
        v /= 10;   //所有价格及金钱都是10倍数
        p *= v;  //重要度乘上价格
        if(q == 0){ //主件
            price[i][0] = v;
            multi_sum[i][0] = p;
        }else{ //附件
            if(price[q][1] == 0){ //第一个附件
                price[q][1] = v;
                multi_sum[q][1] = p;
            }else{ //第二个附件
                price[q][2] = v;
                multi_sum[q][2] = p;
            }
        }
    }
    cout << recursion(m, N, price, multi_sum, dp) * 10 << endl;  //输出要乘回10倍
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(mn\right)O(mn)$O(mn)，其中$n=N/10n=N/10$n=N/10，递归次数相当于遍历dp数组
• 空间复杂度：$O\left(mn\right)O(mn)$O(mn)，最大空间为dp数组的空间

方法三：动态规划空间优化

具体做法：

我们观察到在方法一的状态转移过程中，每次只用第$i-1i-1$i−1个物品的数据，相当于我们只会用两列数据，因此我们可以利用滚动数组代替矩阵，利用$k=0,k=1-kk=0,k=1-k$k=0,k=1−k，不断交换两列的索引即可。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
    int N, m;
    cin >> N >> m;
    N /= 10; //所有价格及金钱都是10倍数
    vector<vector<int> > price(m + 1, vector<int>(3, 0)); //记录价格及附件价格
    vector<vector<int> > multi_sum(m + 1, vector<int>(3, 0)); //记录重要度*价格
    vector<vector<int> > dp(2, vector<int>(N + 1, 0)); //dp数组
    for(int i = 1; i <= m; i++){ //遍历输入，将所有价格及乘积信息录入数组
        int v, p, q;
        cin >> v >> p >> q; //输入价格、重要度、附属信息
        v /= 10;   //所有价格及金钱都是10倍数
        p *= v;  //重要度乘上价格
        if(q == 0){ //主件
            price[i][0] = v;
            multi_sum[i][0] = p;
        }else{ //附件
            if(price[q][1] == 0){ //第一个附件
                price[q][1] = v;
                multi_sum[q][1] = p;
            }else{ //第二个附件
                price[q][2] = v;
                multi_sum[q][2] = p;
            }
        }
    }
    int k = 0;
    for(int i = 1; i <= m; i++){
        k = 1 - k; //滚动数组
        for(int j = 1; j <= N; j++){
            if(j >= price[i][0]) //可以买这个的主件
                dp[k][j] = max(dp[1 - k][j - price[i][0]] + multi_sum[i][0], dp[1 - k][j]); //选择买这个与不买这个的最大值
            else
                dp[k][j] = dp[1 - k][j];
            if(j >= price[i][0] + price[i][1]) //可以买主件 + 第一个附件
                dp[k][j] = max(dp[1 - k][j - price[i][0] - price[i][1]] + multi_sum[i][0] + multi_sum[i][1], dp[k][j]);
            if(j >= price[i][0] + price[i][2]) //可以买主件 + 第二个附件
                dp[k][j] = max(dp[1 - k][j - price[i][0] - price[i][2]] + multi_sum[i][0] + multi_sum[i][2], dp[k][j]);
            if(j >= price[i][0] + price[i][1] + price[i][2]) //可以买主件 + 两个附件
                dp[k][j] = max(dp[1 - k][j - price[i][0] - price[i][1] - price[i][2]] + multi_sum[i][0] + multi_sum[i][1] + multi_sum[i][2], dp[k][j]);
        }
    }
    cout << dp[k][N] * 10 << endl;  //输出要乘回10倍
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(mn\right)O(mn)$O(mn)，其中$n=N/10n=N/10$n=N/10，依旧嵌套两层循环，时间复杂度不变
• 空间复杂度：$O\left(max\right(m,n\left)\right)O(max(m,n))$O(max(m,n))，dp数组缩小为只有两个一维数组，因为还有其他辅助数组在，因此最坏空间取其较大值