网站维护会关闭吗,汽车嵌入式软件开发,优化员工,外国高端网站有依赖的背包是指多个物品变成一个复合物品#xff08;互斥#xff09;#xff0c;每件复合物品不要和怎么要多种可能性展开。时间复杂度O(物品个数 * 背包容量)#xff0c;额外空间复杂度O(背包容量)。
下面通过题目加深理解。 题目一
测试链接#xff1a;[NOIP2006 提…有依赖的背包是指多个物品变成一个复合物品互斥每件复合物品不要和怎么要多种可能性展开。时间复杂度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};
vectorvectorint follows;
int dp[61][32001];
int f(int index, int money){if(index m1){return 0;}if(dp[index][money] ! -1){return dp[index][money];}if(!king[index]){return f(index1, money);}int ans f(index1, money);if(money - cost[index] 0){ans ans f(index1, money-cost[index]) value[index] ?ans : f(index1, money-cost[index]) value[index];}if(fans[index] 1 money - cost[index] - cost[follows[index][0]] 0){ans ans f(index1, money-cost[index]-cost[follows[index][0]]) value[index] value[follows[index][0]] ?ans : f(index1, 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(index1, money-cost[index]-cost[follows[index][1]]) value[index] value[follows[index][1]] ?ans : f(index1, 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(index1, money-cost[index]-cost[follows[index][0]]-cost[follows[index][1]]) value[index] value[follows[index][0]] value[follows[index][1]] ?ans : f(index1, 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);vectorint 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;
}
