题解 | #购物单#

先分解成背包问题，再分解成01背包问题。

因为最多只有2个附件，因此可以分解为以下四种情况：

• 主件
• 主件+附件1
• 主件+附件2
• 主件+附件1+附件2

问题变成一个分组背包问题。分组背包问题可以看成01背包问题。如果你把分组看成是一个物品，而分组中的四个选择，看成物品的四种形态，那其实就是一个01背包问题了。只是当你选择这个物品的时候，你还要再考虑一下，选择物品的哪一个形态能得到最优解。

#include <iostream>
#include <vector>
#include <map>

using namespace std;

const int N = 65;
const int MAX_VALUE = 3205;
int master[N];
int cost[N][3];
int value[N][3];
int dp[MAX_VALUE];

// 分解为分组背包问题，限定了最多只有2个附件，因此可以把它们拆解为：
// 主件 / 主件+附件1 / 主件+附件2 / 主件+附近1+附件2

int main()
{
    int n, m;
    cin >> m >> n;
    m /= 10;
    
    int ic, iv, im;
    for(int i = 1; i <= n; i++)
    {
        cin >> ic >> iv >> im;
        ic /= 10;
        iv *= ic;
        master[i] = im;
        if(im == 0) // 新分组
        {
            cost[i][0] = ic;
            value[i][0] = iv;
            continue;
        }
        if(cost[im][1] == 0) // 非新分组，一个附件也没记录过
        {
            cost[im][1] = ic;
            value[im][1] = iv;
            continue;
        }
        // 新分组，当前是第二个附件
        cost[im][2] = ic;
        value[im][2] = iv;
    }
    
    for(int i = 1; i <= n; i++)
    {
        if(master[i] != 0) continue; // 不是分组
        // 计算四种形态的总价值
        int c0 = cost[i][0], v0 = value[i][0];
        int c1 = cost[i][1], v1 = value[i][1];
        int c2 = cost[i][2], v2 = value[i][2];
        for(int j = m; j >= 0; j--)
        {
            if(j >= c0) // 只买主件
                dp[j] = max(dp[j], dp[j - c0] + v0);
            if(c1 && j >= c0 + c1) // 买主件 + 附件1
                dp[j] = max(dp[j], dp[j - c0 - c1] + v0 + v1);
            if(c2 && j >= c0 + c2) // 买主件 + 附件2
                dp[j] = max(dp[j], dp[j - c0 - c2] + v0 + v2);
            if(c1 && c2 && j >= c0 + c1 + c2) // 买主件 + 附件1 + 附件2
                dp[j] = max(dp[j], dp[j - c0 - c1 - c2] + v0 + v1 + v2);
        }
    }
    int res = 0;
    for(int i = 0; i <= m; i++)
        res = max(res, dp[i]);
    cout << res * 10;
    return 0;
}