HRBUST 1377 金明的预算方案

本文主要是介绍HRBUST 1377 金明的预算方案，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：HRBUST 1377 金明的预算方案

题目大意：

题解：
将主件和其附件分为一组，组内包含主件、主件和附件\(1\)、主件和附件\(2\)、主件和附件\(1,2\)至多四个物品。
对所有组进行\(01\)背包，每组只能选一个。

#include <cstring>
#include <iostream>
using namespace std;

int n, m, w[65][4], v[65][4], dp[32010];

int main() {
    while (cin >> n >> m) {
        memset(dp, 0, sizeof(dp));
        memset(w, 0, sizeof(w));
        memset(v, 0, sizeof(v));
        for (int i = 1, a, b, c; i <= m; ++i) {
            cin >> a >> b >> c;
            if (!c) {  // 是主件
                w[i][0] = a * b;
                v[i][0] = a;
            } else {  // 是附件
                if (!w[c][1]) {
                    w[c][1] = a * b;
                    v[c][1] = a;
                } else {
                    w[c][2] = a * b;
                    v[c][2] = a;
                }
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = n; j >= v[i][0]; --j) {
                dp[j] = max(dp[j], dp[j - v[i][0]] + w[i][0]);  // 只买主件
                // 如果没有相应附件则附件值为0，不影响
                if (v[i][0] + v[i][1] + v[i][2] <= j) {  // 买主件和两个附件
                    dp[j] = max(dp[j], dp[j - v[i][1] - v[i][2] - v[i][0]] + w[i][1] + w[i][2] + w[i][0]);
                }
                if (v[i][0] + v[i][1] <= j) {  // 买主件和一种附件
                    dp[j] = max(dp[j], dp[j - v[i][1] - v[i][0]] + w[i][1] + w[i][0]);
                }
                if (v[i][0] + v[i][2] <= j) {  // 买主件和另一种附件
                    dp[j] = max(dp[j], dp[j - v[i][2] - v[i][0]] + w[i][2] + w[i][0]);
                }
            }
        }
        cout << dp[n] << endl;
    }
    return 0;
}

这篇关于HRBUST 1377 金明的预算方案的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！