首页 > 代码库 > HDu 3449 (有依赖的01背包) Consumer
HDu 3449 (有依赖的01背包) Consumer
题意:
有n件物品,对应有不同的价格和价值,这是典型的01背包。但现在有了一个限制,要买物品先买能装这件物品的特定的盒子,盒子的价值为0
代码理解得还不是太好,感觉这是一个“二重”的01背包。首先假设先买第i个盒子,对每个盒子里的物品进行一次01背包;然后对盒子再进行一次01背包,决策到底要不要买这个盒子
dp[i][j]表示前i个盒子有j元钱能获得的最大价值,则所求就是dp[n][total]
因为物品对盒子有了“依赖”,所以要先对dp赋值为-1,表示买不到盒子就更不可能装物品
这篇题解写的很详细:
http://www.acmerblog.com/hdu-3449-consumer-5475.html
代码虽短,还须多多体会
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 100000 + 10; 8 int dp[52][maxn]; 9 10 int main(void)11 {12 #ifdef LOCAL13 freopen("3449in.txt", "r", stdin);14 #endif15 16 int n, total;17 while(scanf("%d%d", &n, &total) == 2)18 {19 memset(dp, -1, sizeof(dp));20 memset(dp[0], 0, sizeof(dp[0]));21 for(int i = 1; i <= n; ++i)22 {23 int box, m;24 scanf("%d%d", &box, &m);25 for(int j = box; j <= total; ++j)26 dp[i][j] = dp[i - 1][j - box]; //假设先买第i个盒子27 for(int j = 0; j < m; ++j)28 {//对盒子里的物品进行01背包29 int c, w;30 scanf("%d%d", &c, &w); 31 for(int k = total; k >= c; --k)32 if(dp[i][k - c] != -1)33 dp[i][k] = max(dp[i][k], dp[i][k - c] + w);34 }35 for(int j = 0; j <= total; ++j)36 dp[i][j] = max(dp[i][j], dp[i - 1][j]); //决策是否买第i个盒子37 }38 printf("%d\n", dp[n][total]);39 }40 return 0;41 }
另外,可以用滚动数组来优化空间
HDu 3449 (有依赖的01背包) Consumer
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。