HDU 2602 Bone Collector

 1    //01背包入门(一维数组)
 2 1.#include<iostream>  
 3 2.#define maxn 1005  
 4 3.using namespace std;  
 5 4.int v[maxn],w[maxn],dp[maxn];  
 6 5.int max(int a,int b)  
 7 6.{  
 8 7.    return a>b?a:b;  
 9 8.}  
10 9.int main()  
11 10.{  
12 11.    //freopen("1002.txt","r",stdin);  
13 12.    int t,n,m,i,j;  
14 13.    while(~scanf("%d",&t))  
15 14.    {  
16 15.        while(t--)  
17 16.        {  
18 17.            memset(v,0,sizeof(v));  
19 18.            memset(w,0,sizeof(w));  
20 19.            memset(dp,0,sizeof(dp));  
21 20.            scanf("%d%d",&n,&m);  
22 21.            for(i=0;i<n;i++)  
23 22.                scanf("%d",w+i);  
24 23.            for(i=0;i<n;i++)  
25 24.                scanf("%d",v+i);  
26 25.            for(i=0;i<n;i++)  
27 26.                for(j=m;j>=v[i];j--)  //j表示当前背包剩余容量
28 27.                    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);  //dp[j-v[i]+w[i]]代表装入第i件物品
29 28.                printf("%d ",dp[m]);  
30 29.        }  
31 30.          
32 31.    }  
33 32.    return 0;  
34 33.}