题目分析

1. 题目其实是01背包问题的变形，给出了两种类的输入信息
2. 题目输入的第一行信息表示预算和数量的要求，购买的物品不能超过预算，并且购买的数量有限制
3. 后面的输入内容是物品的详情信息，包括价格、权值、主件附件关系
4. 此题要求特殊的一点是如果购买了附件产品，必须含带着主件产品一起购买。也就是说买附件必须买主件，但是买主件不一定需要买附件
5. 同时要保证购买到的物品加权价格后的总和要是最大的，返回这个最大的加权价格结果

方法一：动态规划

• 实现思路
  • 我们规定dp[i][j]表示在 [ 前i ] 个物品里面 [ 预算值（背包）容量允许为j ] 的情况下可以获得的最大的价值加权和
  • 对于01背包问题，我们的动态规划决策是当前物品是否要选择。
    $dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[j]]+v[j])dp[i][j]\; =\; max(dp[i-1][j],\; dp[i-1][j-w[j]]\; +\; v[j])$
  • 但是由于本题有主附件的选择考虑，因此我们将选择的情况划分为更多种类
    • 不选择当前物品
    • 选择【当前主件物品】
    • 选择【当前主件 + 附件1】
    • 选额【当前主件 + 附件2】
    • 选择【当前主件 + 附件1 + 附件2】
  • 因此有动态转移方程
  $dp[i][j]=max(dp[i-1][j],\mathrm{四}\mathrm{种}\mathrm{选}\mathrm{择}\mathrm{方}\mathrm{案})dp[i][j]\; =\; max(dp[i-1][j],\; 四种选择方案)$

  • 同时本题处理上的一个关键内容在于如何访问我们的所有物品。依据我们的方案，我们需要将物品重新处理成新的数据结构，这种结构要求一定是主件优先被访问到，并且绑定主件和附件的关系

  • 并且由于价格都是10的整数倍，我们统一在数据处理的时候都缩小十倍处理

• 因此我们有如下的表格结构

假设现在的输入内容为

50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0

重新组织结构后（价格和加权价值全部是除以10后的结果）

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int N, m, v, p, q;;
    cin >> N >> m;
    N /= 10;
    
    // 重新处理数据，整理成  "主件(价格+加权价值)+附件1(价格+加权价值)+附件2(价格+加权价值)"  的结构
    vector<vector<int>> items(m + 1, vector<int>(6, 0));
    
    for(int i = 1; i <= m; i++) {
        cin >> v >> p >> q;    // 价格 权重 主附
        v /= 10;
        p *= v;
        if(q == 0) {                        // 如果当前是主件
            items[i][0] = v;
            items[i][1] = p;
        } else if(items[q][2] == 0) {       // 如果当前附件1位置为空
            items[q][2] = v;
            items[q][3] = p;
        } else {                            // 只剩下附件2的位置
            items[q][4] = v;
            items[q][5] = p;
        }
    }
    
    vector<vector<int>> dp(m + 1, vector<int>(N + 1, 0));
    // dp[i][j] 表示在前i个里面预算值（背包）容量允许为j的情况下可以获得的最大的价值加权和
    
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= N; j++) {
            int a = items[i][0], d = items[i][1];    // 主件的价格+加权价值
            int b = items[i][2], e = items[i][3];    // 附件1的价格+加权价值
            int c = items[i][4], f = items[i][5];    // 附件2的价格+加权价值
            
            dp[i][j] = dp[i-1][j];
            if(j >= a) dp[i][j] = max(dp[i-1][j-a] + d, dp[i-1][j]);				// 只挑选一个主件
            if(j >= a+b) dp[i][j] = max(dp[i-1][j-a-b] + d+e, dp[i][j]);			// 挑选主件+附件1
            if(j >= a+c) dp[i][j] = max(dp[i-1][j-a-c] + d+f, dp[i][j]);			// 挑选主件+附件2
            if(j >= a+b+c) dp[i][j] = max(dp[i-1][j-a-b-c] + d+e+f, dp[i][j]);	// 挑选主件+附件1+附件2
            
        }
    }
    cout << dp[m][N] * 10 <<endl;
    return 0;
}

复杂度分析

• 时间复杂度：$O(mN)O(mN)$，要维护这个二位dp矩阵的时间代价
• 空间复杂度：$O(mN)O(mN)$，二维矩阵dp的空间开销

方法二：动态规划+空间优化

• 实现思路

  • 我们可以发现对于任意一次dp[i][j]的更新，都只和其相邻的[i-1]行有关

  • 因此我们可以用一维空间来减少空间开销

  • 为了不破坏所谓的上一行的数据信息，在更新迭代的时候要从一维数组的末尾遍历更新到首端

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int N, m, v, p, q;;
    cin >> N >> m;
    N /= 10;
    
    // 重新处理数据，整理成  "主件(价格+加权价值)+附件1(价格+加权价值)+附件2(价格+加权价值)"  的结构
    vector<vector<int>> items(m + 1, vector<int>(6, 0));
    
    for(int i = 1; i <= m; i++) {
        cin >> v >> p >> q;    // 价格 权重 主附
        v /= 10;
        p *= v;
        if(q == 0) {                        // 如果当前是主件
            items[i][0] = v;
            items[i][1] = p;
        } else if(items[q][2] == 0) {       // 如果当前附件1位置为空
            items[q][2] = v;
            items[q][3] = p;
        } else {                            // 只剩下附件2的位置
            items[q][4] = v;
            items[q][5] = p;
        }
    }
    
    vector<int> dp(N+1, 0);
    // dp[j] 表示预算值（背包）容量允许为j的情况下可以获得的最大的价值加权和
    
    for(int i = 1; i <= m; i++) {
        for(int j = N; j >= 1; j--) {				// 从末尾遍历到首端
            int a = items[i][0], d = items[i][1];    // 主件的价格+加权价值
            int b = items[i][2], e = items[i][3];    // 附件1的价格+加权价值
            int c = items[i][4], f = items[i][5];    // 附件2的价格+加权价值
            
            dp[j] = dp[j];
            if(j >= a) dp[j] = max(dp[j-a] + d, dp[j]);
            if(j >= a+b) dp[j] = max(dp[j-a-b] + d+e, dp[j]);
            if(j >= a+c) dp[j] = max(dp[j-a-c] + d+f, dp[j]);
            if(j >= a+b+c) dp[j] = max(dp[j-a-b-c] + d+e+f, dp[j]);
            
        }
    }
    cout << dp[N] * 10 <<endl;
    return 0;
}

复杂度分析

• 时间复杂度：$O(mN)O(mN)$，时间代价还是相同的开销
• 空间复杂度：$O(N)O(N)$，空间代价我们省到了一维