题解 | 购物单 非常繁琐的01背包问题

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

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

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

int main() {
    int Money;
    int Count;

    while (cin >> Money >> Count) {
        Money /= 10;
        vector<vector<int>> Info(Count + 1, vector<int>(3, 0));
        vector<int> main;
        unordered_map<int, vector<int>> Main_connection;
        for (int i = 1; i <= Count; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            Info[i][0] = a / 10;
            Info[i][1] = b;
            Info[i][2] = c;
            if (c == 0) {
                main.push_back(i);
            }
            if (c != 0) {
                Main_connection[c].push_back(i);
            }
        }
        vector<int> value(Count + 1, 0);
        for (int i = 1; i <= Count; i++) {
            value[i] = Info[i][0] * Info[i][1];
        }
        vector<vector<int>> dp(main.size() + 1, vector<int>(Money + 1, 0));

        for (int i = 1; i <= main.size(); i++) {
            int main_id = main[i - 1];
            for (int j = 0; j <= Money; j++) {
                // 不选当前主件
                dp[i][j] = dp[i - 1][j];

                // 选当前主件
                if (j >= Info[main_id][0]) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - Info[main_id][0]] + value[main_id]);
                }

                // 选当前主件 + 附件 1
                if (Main_connection[main_id].size() >= 1 && j >= Info[main_id][0] + Info[Main_connection[main_id][0]][0]) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - Info[main_id][0] - Info[Main_connection[main_id][0]][0]] + value[main_id] + value[Main_connection[main_id][0]]);
                }

                // 选当前主件 + 附件 2
                if (Main_connection[main_id].size() >= 2 && j >= Info[main_id][0] + Info[Main_connection[main_id][1]][0]) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - Info[main_id][0] - Info[Main_connection[main_id][1]][0]] + value[main_id] + value[Main_connection[main_id][1]]);
                }

                // 选当前主件 + 附件 1 + 附件 2
                if (Main_connection[main_id].size() >= 2 && j >= Info[main_id][0] + Info[Main_connection[main_id][0]][0] + Info[Main_connection[main_id][1]][0]) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - Info[main_id][0] - Info[Main_connection[main_id][0]][0] - Info[Main_connection[main_id][1]][0]] + value[main_id] + value[Main_connection[main_id][0]] + value[Main_connection[main_id][1]]);
                }
            }
        }
        cout << dp[main.size()][Money] * 10 << endl;
    }
}
// 64 位输出请用 printf("%lld")