SOJ 4580 动态规划之01背包 （01背包）

Description

　　Sidney想去Gandtom家玩。但Sidney家和Gandtom家之间是高低不平、坑坑洼洼的土路。所以他需要用他的背包装几袋稀的泥，在路上铺平一些干的土，使路变成平整的泥土，才能到Gandtom家见到Gandtom。 
　　已知现在有种稀的泥，第种稀的泥的质量为，体积为，数量为。Sidney的包能装体积不超过的稀的泥。Sidney出门时携带的稀的泥的质量应该尽可能的大。在此前提下，携带的稀的泥的体积也应该尽可能的大。 
　　试求Sidney最多能携带多少质量的稀的泥与此时的最大体积上路。

 

Input

第一行有一个整数，表示组数。 
每组数据第一行有两个正整数、 。 
每组数据第二行有个正整数，第个数为。 
每组数据第三行有个正整数，第个数为。

 

Output

每组样例第一行输出两个整数。表示Sidney最多能携带多少质量的稀的泥与此时的最大体积上路。

 

Sample Input

2 
5 3 
1 2 3 4 5 
1 1 1 1 1 
3 7 
1 2 1 
3 5 3

 

Sample Output

12 3 
2 6

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <math.h>

#include <algorithm>

using namespace std;

int dp[],w[],v[];

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        memset(dp,,sizeof(dp));

        int n,V,i,j,max1=,maxpos=;

        scanf("%d%d",&n,&V);

        for(i=;i<=n;i++)

          scanf("%d",&w[i]);

        for(i=;i<=n;i++)

          scanf("%d",&v[i]);

        dp[v[]]=w[];

        for(i=;i<=n;i++)

          for(j=V;j>=v[i];j--)

            if(j==v[i]||dp[j-v[i]])

              dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

        for(i=V;i>;i--)

          if(dp[i]>max1){

              max1=dp[i];

              maxpos=i;

          }

       printf("%d %d\n",max1,maxpos);

    }

    return ;

}