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

fiwhgikbl

一、题目解读

牛客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]为最终答案。

四、代码与注释

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. struct Item {
   
7.     int v, w, q; // 价格、重要度、主件ID
   
8.     int value;   // v*w
   
9. };
   
10. 
    
11. int main() {
    
12.     int budget, m;
    
13.     cin >> budget >> m;
    
14.    
    
15.     vector<Item> items(m+1); // 物品列表(1-based)
    
16.     vector<vector<int>> att(m+1); // 主件的附件索引
    
17.    
    
18.     // 输入处理
    
19.     for(int i = 1; i <= m; i++) {
    
20.         cin >> items[i].v >> items[i].w >> items[i].q;
    
21.         items[i].value = items[i].v * items[i].w;
    
22.         if(items[i].q) att[items[i].q].push_back(i); // 附件存入对应主件索引
    
23.     }
    
24.    
    
25.     vector<int> dp(budget+1, 0); // 动态规划数组，dp[j]表示预算j下的**价值
    
26.    
    
27.     for(int i = 1; i <= m; i++) {
    
28.         if(items[i].q) continue; // 仅处理主件
    
29.         
    
30.         int v0 = items[i].v, w0 = items[i].value; // 主件信息
    
31.         vector<pair<int,int>> options; // 组合列表（价格,价值）
    
32.         options.emplace_back(v0, w0); // 仅主件组合
    
33.         
    
34.         // 生成所有有效组合
    
35.         if(att[i].size() >= 1) {
    
36.             int v1 = items[att[i][0]].v, w1 = items[att[i][0]].value;
    
37.             options.emplace_back(v0+v1, w0+w1); // 主件+附件1
    
38.         }
    
39.         if(att[i].size() >= 2) {
    
40.             int v2 = items[att[i][1]].v, w2 = items[att[i][1]].value;
    
41.             options.emplace_back(v0+v2, w0+w2); // 主件+附件2
    
42.             if(att[i].size() >= 1) {
    
43.                 int v1 = items[att[i][0]].v, w1 = items[att[i][0]].value;
    
44.                 options.emplace_back(v0+v1+v2, w0+w1+w2); // 主件+附件1+附件2
    
45.             }
    
46.         }
    
47.         
    
48.         // 01背包处理
    
49.         for(int j = budget; j >= 0; j--) {
    
50.             for(auto &opt : options) {
    
51.                 if(j >= opt.first) { // 若预算足够
    
52.                     dp[j] = max(dp[j], dp[j-opt.first] + opt.second); // 状态转移
    
53.                 }
    
54.             }
    
55.         }
    
56.     }
    
57.    
    
58.     cout << dp[budget] << endl; // 输出最终结果
    
59.     return 0;
    
60. }

复制代码

五、总结

本解法通过巧妙组合生成将复杂依赖转化为01背包问题，时间复杂度O(m^2*budget)，空间复杂度O(budget)。关键在于准确处理附件与主件的组合逻辑，避免重复计算。对于类似依赖关系的选择问题，此思路具备通用性，可扩展至其他优化场景。

来源：牛客网题解