题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3449
题目翻译:
有N个盒子,每个盒子价值是p,其内部有m个物品,每个物品的花费为c,价值为p.
如果想要购买盒子内的物品,就必须先花钱买盒子。
所以对于某个盒子来所,我们分为买与不买,首先我们备份其没买时候的值,
然后考虑买这个盒子,如果买盒子的话,则先减去买盒子的钱。然后对m个
物品进行0,1背包,跑完之后和原备份数组中的值比较,看看是买这个盒子
获得的钱多还是不买获得的钱多。
这个是有依赖关系的背包。
AC代码:
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; int N,W; ///盒子数和钱数 int dp[100010]; int temp[100010]; int cost[52],value[52]; int main() { while(~scanf("%d%d",&N,&W)) { memset(dp,sizeof(dp)); memset(temp,sizeof(temp)); for(int i = 1; i <= N; i++) { int p,m; scanf("%d%d",&p,&m); ///这个盒子是p元钱,里面有m件物品 for(int j = 1; j <= m; j++) { scanf("%d%d",&cost[j],&value[j]); } ///要买第i箱东西。需要先买第i个箱子 for(int j = p; j <= W; j++) { dp[j] = temp[j-p]; } for(int j = 1; j <= m; j++) { for(int k = W; k >=cost[j]+p; k--) { dp[k] = max(dp[k],dp[k-cost[j]] + value[j]); } } for(int j = 0; j <= W; j++) { temp[j] = max(dp[j],temp[j]); } } printf("%d\n",temp[W]); } return 0; }原文链接:https://www.f2er.com/javaschema/282472.html