当前位置：首页 > 牛客 > 背包问题优化：动态规划解决主件附件选择难题（牛客4802题解题全解析）

背包问题优化：动态规划解决主件附件选择难题（牛客4802题解题全解析）

5个月前 (07-17)

一、题目解读

牛客4802题要求在一个预算限制下，从包含主件和附件的物品列表中选择组合，最大化总价值。每个主件可附带多个附件，选择附件的前提是必须选择对应主件。题目本质是经典的01背包问题的扩展，需处理主件与附件的依赖关系，并优化组合选择策略。

二、解题思路

核心思想是将附件组合与主件形成“虚拟物品”，再通过01背包求解。

1. 主件与附件依赖建模：使用Item结构存储物品信息（价格v、重要度w、主件ID q），并通过att数组记录每个主件的附件索引。

2. 组合生成：对每个主件，生成四种组合（仅主件、主件+附件1、主件+附件2、主件+附件1+附件2）。

3. 动态规划：构建dp数组，状态转移方程dp[j] = max(dp[j], dp[j-opt.first] + opt.second)，实现01背包优化。

三、解题步骤

1. 输入处理：读入预算budget和物品数量m，构建items和att数组，计算物品价值value = v * w。

2. 组合构建：遍历主件，根据附件数量生成1~4种组合（避免重复），存入options向量。

3. 动态规划：倒序遍历预算，对每个组合更新dp值，取最大值。

4. 输出结果：dp[budget]为最终答案。

四、代码与注释

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

struct Item {
    int v, w, q; // 价格、重要度、主件ID
    int value;   // v*w
};

int main() {
    int budget, m;
    cin >> budget >> m;
    
    vector<Item> items(m+1); // 物品列表(1-based)
    vector<vector<int>> att(m+1); // 主件的附件索引
    
    // 输入处理
    for(int i = 1; i <= m; i++) {
        cin >> items[i].v >> items[i].w >> items[i].q;
        items[i].value = items[i].v * items[i].w;
        if(items[i].q) att[items[i].q].push_back(i); // 附件存入对应主件索引
    }
    
    vector<int> dp(budget+1, 0); // 动态规划数组，dp[j]表示预算j下的最大价值
    
    for(int i = 1; i <= m; i++) {
        if(items[i].q) continue; // 仅处理主件
        
        int v0 = items[i].v, w0 = items[i].value; // 主件信息
        vector<pair<int,int>> options; // 组合列表（价格,价值）
        options.emplace_back(v0, w0); // 仅主件组合
        
        // 生成所有有效组合
        if(att[i].size() >= 1) {
            int v1 = items[att[i][0]].v, w1 = items[att[i][0]].value;
            options.emplace_back(v0+v1, w0+w1); // 主件+附件1
        }
        if(att[i].size() >= 2) {
            int v2 = items[att[i][1]].v, w2 = items[att[i][1]].value;
            options.emplace_back(v0+v2, w0+w2); // 主件+附件2
            if(att[i].size() >= 1) {
                int v1 = items[att[i][0]].v, w1 = items[att[i][0]].value;
                options.emplace_back(v0+v1+v2, w0+w1+w2); // 主件+附件1+附件2
            }
        }
        
        // 01背包处理
        for(int j = budget; j >= 0; j--) {
            for(auto &opt : options) {
                if(j >= opt.first) { // 若预算足够
                    dp[j] = max(dp[j], dp[j-opt.first] + opt.second); // 状态转移
                }
            }
        }
    }
    
    cout << dp[budget] << endl; // 输出最终结果
    return 0;
}