首页 > 代码库 > HDu 3449 (有依赖的01背包) Consumer

HDu 3449 (有依赖的01背包) Consumer

2024-07-21 17:47:04   219人阅读

题意：

有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


联系
我们