动态规划进阶：牛客4802题带附件背包问题详解 | 组合优化技巧
一、问题背景与算法思路
牛客4802题是一个典型的带附件的背包问题变种，要求在主件和附件存在依赖关系的情况下，选择物品组合使总价值最大化。本文通过动态规划方法，将问题转化为分组背包问题，通过预处理所有可能的组合方式来实现高效求解。
二、完整代码实现（带详细注释）
#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数组 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) { // 主件+附件1 int v1 = items[att[i][0]].v, w1 = items[att[i][0]].value; options.emplace_back(v0+v1, w0+w1); } if(att[i].size() >= 2) { // 主件+附件2 和 主件+附件1+附件2 int v2 = items[att[i][1]].v, w2 = items[att[i][1]].value; options.emplace_back(v0+v2, w0+w2); 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); } } // 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; }
三、关键算法要点
组合预处理：为每个主件生成所有可能的有效组合（主件、主件+附件1、主件+附件2、主件+附件1+附件2）
动态规划处理：采用01背包思路，但每个主件及其组合作为一个"组"来处理
四、复杂度分析
时间复杂度：O(budgetm4) ≈ O(n²)（最坏情况每个主件有2个附件）
空间复杂度：O(budget)（仅需一维DP数组）
五、常见错误提醒
忘记处理主附件关系导致逻辑错误
组合生成不完整（漏掉某些有效组合）
背包DP数组初始化错误
输入处理时索引越界
六、学习价值
通过本题可以掌握：
带依赖关系的背包问题解法
动态规划的状态转移优化
分组背包问题的变种解法
组合预处理技巧在实际问题中的应用
原创内容 转载请注明出处
