算法【有依赖的背包】

有依赖的背包是指多个物品变成一个复合物品（互斥），每件复合物品不要和怎么要多种可能性展开。时间复杂度O(物品个数 * 背包容量)，额外空间复杂度O(背包容量)。

下面通过题目加深理解。

题目一

测试链接：[NOIP2006 提高组] 金明的预算方案 - 洛谷

分析：对于这道题，可以参考01背包是对每个物品进行可能性的展开，有依赖的背包是对主件进行可能性的展开，所以可能性就比01背包的展开多。对于一个没有附件的主件可能性的展开，就是01背包的展开，即选或不选主件。对于有一个附件的主件可能性的展开，就有三种，选主件、不选主件、主件和附件一起选。对于有两个附件的主件可能性的展开，就有五种，选主件、不选主件、主件和第一个附件一起选、主件和第二个附件一起选、主件和两个附件一起选。对于输入，代码中采用了几个数组结构存储信息，cost数组存储花费代价，value数组存储收益，king数组存储是否是主件，fans数组存储主件有多少个附件，follows数组存储每个主件拥有的附件。下面代码采用计划搜索，并没有去做空间压缩，代码如下。

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int cost[61];
int value[61];
bool king[61];
int fans[61] = {0};
vector<vector<int>> follows;
int dp[61][32001];
int f(int index, int money){if(index == m+1){return 0;}if(dp[index][money] != -1){return dp[index][money];}if(!king[index]){return f(index+1, money);}int ans = f(index+1, money);if(money - cost[index] >= 0){ans = ans > f(index+1, money-cost[index]) + value[index] ?ans : f(index+1, money-cost[index]) + value[index];}if(fans[index] >= 1 && money - cost[index] - cost[follows[index][0]] >= 0){ans = ans > f(index+1, money-cost[index]-cost[follows[index][0]]) + value[index] + value[follows[index][0]] ?ans : f(index+1, money-cost[index]-cost[follows[index][0]]) + value[index] + value[follows[index][0]];}if(fans[index] == 2){if(money - cost[index] - cost[follows[index][1]] >= 0){ans = ans > f(index+1, money-cost[index]-cost[follows[index][1]]) + value[index] + value[follows[index][1]] ?ans : f(index+1, money-cost[index]-cost[follows[index][1]]) + value[index] + value[follows[index][1]];}if(money - cost[index] - cost[follows[index][0]] - cost[follows[index][1]] >= 0){ans = ans > f(index+1, money-cost[index]-cost[follows[index][0]]-cost[follows[index][1]]) + value[index] + value[follows[index][0]] + value[follows[index][1]] ?ans : f(index+1, money-cost[index]-cost[follows[index][0]]-cost[follows[index][1]]) + value[index] + value[follows[index][0]] + value[follows[index][1]];}}dp[index][money] = ans;return ans;
}
int main(void){int v, p, q;scanf("%d%d", &n, &m);vector<int> temp;for(int i = 0;i <= m;++i){follows.push_back(temp);}for(int i = 1;i <= m;++i){scanf("%d%d%d", &v, &p, &q);cost[i] = v;value[i] = v * p;if(q != 0){king[i] = false;fans[q]++;follows[q].push_back(i);}else{king[i] = true;}}for(int i = 1;i < 61;++i){for(int j = 1;j < 32001;++j){dp[i][j] = -1;}}printf("%d", f(1, n));return 0;
}