hdu4501——小明系列故事——买年货（多维背包）-白红宇

hdu4501——小明系列故事——买年货（多维背包）

阅读量：5103 次

发布时间：2019-06-13

本文共 1546 字，大约阅读时间需要 5 分钟。

题解：

思路：将v1,v2，k都当作一种体积，开三维dp数组，每种物品只能取一次

代码中的for循环是倒着进行的，知道01背包和完全背包的肯定明白，倒着进行的就代表每种物品只选择一次

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int maxn=105; 7 const int INF=0x3f3f3f3f; 8 int dp[maxn][maxn][6]; 9 struct shudui10 {11     int a,b,val;12 } m[maxn];13 int main()14 {15     int n,v1,v2,k1;16     while(~scanf("%d%d%d%d",&n,&v1,&v2,&k1))17     {18         for(int i=1; i<=n; ++i)19         {20             scanf("%d%d%d",&m[i].a,&m[i].b,&m[i].val);21         }22         memset(dp,0,sizeof(dp));23         for(int l=1; l<=n; ++l)24         {25             for(int i=v1; i>=0; --i)26             {27                 for(int j=v2; j>=0; --j)28                 {29                     for(int k=k1; k>=0; --k)30                     {31                         int temp=0;32                         if(i-m[l].a>=0)33                             temp=max(temp,dp[i-m[l].a][j][k]+m[l].val);34                         if(j-m[l].b>=0)35                             temp=max(temp,dp[i][j-m[l].b][k]+m[l].val);36                         if(k>0)37                             temp=max(temp,dp[i][j][k-1]+m[l].val);38                             dp[i][j][k]=max(dp[i][j][k],temp);39                     }40                 }41             }42         }43         printf("%d\n",dp[v1][v2][k1]);44     }45     return 0;46 }