题解 | #购物单#

源代码来源：https://blog.nowcoder.net/n/9b7b33dfa9cc4956853dfb52de0c2de9?f=comment

注释中解释说明了对代码的理解

// 题目来源：华为机试——牛客HJ16——购物单
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N, m;
    cin >> N >> m;
    // 由于价格是10的整数倍，处理一下以降低空间/时间复杂度
    N /= 10;
    // 主件 附件1 附件2 
    vector<vector<int>> prices(61, vector<int>(3, 0));
    // 重要程度：以主件 附件1 附件2形式存储
    vector<vector<int>> priceMultiplyPriority(61, vector<int>(3, 0));
    for (int i = 1; i <= m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a /= 10;
        b *= a;
        if (c == 0)//主件
        {                                    
            prices[i][0] = a;                //第一件物品价值/10
            priceMultiplyPriority[i][0] = b; //幸福度
        }
        else//附件
        { 
            if (prices[c][1] == 0)//附件1
            {
                prices[c][1] = a;
                priceMultiplyPriority[c][1] = b;
            }
            else//附件2
            {
                prices[c][2] = a;
                priceMultiplyPriority[c][2] = b;
            }
        }
    }
    // 使用分组背包
    //N为总金额，m为物品数量
    vector<vector<int>> dp(m + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= m; ++i)//物品
    {
        for (int j = 1; j <= N; ++j)//背包
        {
            //a为第一个物品主件的价格，b为第一个物品主件的幸福度
            //c为第一个物品附件1的价格，d为第一个物品附件1的幸福度
            //e为第一个物品附件2的价格，f为第一个物品附件2的幸福度
            int a = prices[i][0], b = priceMultiplyPriority[i][0];
            int c = prices[i][1], d = priceMultiplyPriority[i][1];
            int e = prices[i][2], f = priceMultiplyPriority[i][2];
            //j>=a表示取max(上一个背包容量为j-a时的最大幸福度+第一件物品主件的幸福度，上一个背包容量为j的幸福度)
            //j<a表示当前金额小于物品价格，保持上一次的幸福度不变
            dp[i][j] = j >= a ? max(dp[i - 1][j - a] + b, dp[i - 1][j]) : dp[i - 1][j];
            //取主件和附件1的情况
            //如果a+c>j，则保持情况1的当前最大值
            dp[i][j] = j >= (a + c) ? max(dp[i - 1][j - a - c] + b + d, dp[i][j]) : dp[i][j];
            //取主件和附件2的情况
            //如果a+e>j，则保持情况1的当前最大值
            dp[i][j] = j >= (a + e) ? max(dp[i - 1][j - a - e] + b + f, dp[i][j]) : dp[i][j];
            //取主件、附件1和附件2的情况
            //如果a+c+e>j，则保持情况1的当前最大值
            dp[i][j] = j >= (a + c + e) ? max(dp[i - 1][j - a - c - e] + b + d + f, dp[i][j]) : dp[i][j];
        }
    }
    cout << dp[m][N] * 10 << endl;
}