題意：每一組物品都有一個盒子，要買該組的物品必須先要買盒子，問能夠獲得的價值最大是多少。

解題思路：這題有點像分組背包，但是每一組里面要買物品必須要先買盒子。其實我的想法還是和分組背包的思路一樣，只是把盒子看成一個單獨的物品，dp[i][j]表示前i組物品，容量為j時的最大價值。為了防止盒子沒有買就買了這一組的物品，我們最開始的dp[i][j]賦值為-1，在該組里做一次01背包，同樣，還是需要做一次分類，該組里面的物品是第一個放入的還是之前已放入過其他物品。但如果認為這樣就完成任務了，那么就game over了，如果該組沒有一個放入背包，那么dp[i]的所有值都會為-1，連之前的狀態(tài)都會丟失，所以還要把之前的值復制過來。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;int n,m,box[55],cost[55][11],value[55][11]; int dp[55][100005],num[55];int main() {while(scanf("%d%d",&n,&m)!=EOF){memset(dp,-1,sizeof(dp));memset(dp[0],0,sizeof(dp[0]));for(int i = 1; i <= n; i++){scanf("%d",&box[i]);scanf("%d",&num[i]);for(int j = 1; j <= num[i]; j++)scanf("%d%d",&cost[i][j],&value[i][j]);}int ans = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= num[i]; j++)for(int v = m; v >= cost[i][j]; v--){if(dp[i][v-cost[i][j]] != -1) //之前就放過物品了，直接01背包dp[i][v] = max(dp[i][v],dp[i][v-cost[i][j]]+value[i][j]);if(v >= box[i] + cost[i][j]) //該組里面第一個放入背包的物品{if(dp[i-1][v-box[i]-cost[i][j]] != -1)dp[i][v] = max(dp[i][v],dp[i-1][v-box[i]-cost[i][j]]+value[i][j]);}}for(int v = 0; v <= m; v++)dp[i][v] = max(dp[i][v],dp[i-1][v]);}printf("%d\n",dp[n][m]);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 3449(依赖背包)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。