hdu 2602 Bone Collector 0-1背包；-白红宇

hdu 2602 Bone Collector 0-1背包；

阅读量：4113 次

发布时间：2019-05-25

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

题意：n件物品，每件物品都有价值value和体积volume，求一个容积v的背包最多能装的价值；

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               using namespace std;#define MM(a) memset(a,0,sizeof(a))typedef long long ll;typedef unsigned long long ULL;const int mod = 1000000007;const double eps = 1e-10;const int inf = 0x3f3f3f3f;const int big=50000;int value[1005],volume[1005],dp[1005][1005];int main(){ int cas; cin>>cas; while(cas--) { int n,vl; scanf("%d %d",&n,&vl); for(int i=1;i<=n;i++) scanf("%d",&value[i]); for(int i=1;i<=n;i++) scanf("%d",&volume[i]); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=0;j<=vl;j++) if(j>=volume[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-volume[i]]+value[i]); else dp[i][j]=dp[i-1][j]; printf("%d\n",dp[n][vl]); } return 0;}