题解 | 购物单

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

vector<vector<int>> info;
vector<vector<int>> priceV;
vector<vector<int>> valueV;
map<vector<int>, int> mapDp;
int dfs(int i, int c)
{
    if(i < 0) return 0;
    vector<int> key = {i, c};
    if(mapDp.find(key) != mapDp.end()) {
        return mapDp[key];
    }

    int resUnSel = 0;
    int resSel = 0;
   
    // 不选，找出前（i - 1）个预算不大于c的最大价值
    resUnSel = dfs(i - 1, c);

    // 选, 算出前（i - 1）个预算不大于（c - ci）的最大价值
    bool isAttach = (info.at(i).at(2) != 0);
    if(isAttach) {
        // 附件跳过
        goto EXIT;
    } else {
        for (size_t j = 0; j < 4; j++) {
            if(priceV[i][j] == 0) break;
            if(c < priceV[i][j]) continue;
            resSel = max(dfs(i - 1, c - priceV[i][j])+valueV[i][j], resSel);
        }
    }

EXIT:
    int res = max(resSel, resUnSel);
    mapDp[key] = res;
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    priceV.resize(m, vector<int>(4, 0));
    valueV.resize(m, vector<int>(4, 0));

    for (size_t i = 0; i < m; i++) {
        int price, importance, mainNum;
        cin >> price >> importance >> mainNum;
        vector<int> tmp = {price, importance, mainNum};
        info.push_back(tmp);

        // 主件
        if(mainNum == 0) {
            priceV[i][0] = price;
            valueV[i][0] = price * importance;
        }
        // 附件1
        else if(priceV[mainNum - 1][1] == 0) {
            priceV[mainNum - 1][1] = price;
            valueV[mainNum - 1][1] = price * importance;
        }
        else {
            // 附件2
            priceV[mainNum - 1][2] = price;
            valueV[mainNum - 1][2] = price * importance;
            // 附件1 + 2
            priceV[mainNum - 1][3] = priceV[mainNum - 1][1] + priceV[mainNum - 1][2];
            valueV[mainNum - 1][3] = valueV[mainNum - 1][1] + valueV[mainNum - 1][2];
        }
    }
    // 将主件的价格和价值，添加到附件的组合中
    for (size_t i = 0; i < m; i++) {
        for(int j = 1 ; j < 4 ; j++) {
            priceV[i][j] += priceV[i][0];
            valueV[i][j] += valueV[i][0];
        }
    }

    int maxValue = dfs(m - 1, n);
    cout << maxValue;
}

0-1背包问题，用递归求解。主要思路是：

对于第i个物品，价格为p，剩余预算为c，有两种情况：

1.不选择物品i, 可算出最大价值为：前（i-1）个物品在预算为c下的最大价值；

2.选择物品i，可算出最大价值为：前（i-1）个物品在预算为(c-p)下的最大价值 + 当前物品价值。

取两种情况中价值最大的一种返回，即通过 i 和 c 两个参数可递归求出 i 个物品在预算为 c 下的最大价值。

由于递归时会有很多重复的可能，可以（i，c）为key将已递归过的同样情况保存到map中，再次递归时直接返回。

因为有附件的存在，所以需要先将问题简化。

附件需依赖主件存在，且最多2个附件，则主件选择情况有四种：1.主件；2.主件+附件1；3.主件+附件2；4.主件+附件1+附件2。

所以可在递归时跳过附件的遍历，而选择主件时，依次遍历这四种情况，在其中选择最大价值的一种即可。