Bone Collector

许多年前，在泰迪的家乡有一个人，他被称为“骨头收藏家”。这个人喜欢收集各种各样的骨头，比如狗的，牛的，他也去了坟墓… 收集骨头的人有一个体积为V的大袋子，在他收集的过程中有很多骨头，很明显，不同的骨头有不同的价值，不同的体积，现在给出每根骨头在他的过程中的价值，你能计算出收集骨头的人能得到的最大总价值吗？

Input

第一行包含整数T，即案例数。 其次是T例，每例三行，第一行包含两个整数N，V，（N <= 1000，V <= 1000）代表他的骨数和包的体积。第二行包含N个整数，表示每个骨骼的值。第三行包含N个整数，表示每个骨骼的体积。

Output

每行一个整数表示总价值的最大值（这个数字将小于2^31）。

Sample Input

1
2
3
4

1
5 10
1 2 3 4 5
5 4 3 2 1

Sample Output

1

14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include<iostream>
using namespace std;
int T,w[1010],t[1010],f[1010][1010];
int main(){
	cin>>T;
	while(T--){
		int N,V;
		cin>>N>>V;
		for(int i=1;i<=N;i++)
			cin>>w[i];
		for(int i=1;i<=N;i++)
			cin>>t[i];
	for(int i=1;i<=N;i++){
	for(int j=0;j<=V;j++){
		f[i][j]=f[i-1][j];
		if(j>=t[i]){
			int k=f[i-1][j-t[i]]+w[i];
            //如果第i件物品放入背包，则f[i][j]=f[i-1][j-v[i]]+w[i];
  //如果第i件物品放入背包，则背包容量还剩j-v[i],所以要取前i-1件物品放入背包剩余容量j-v[i]所获得的最大价值f[i-1] [j-v[i]];
			int l=f[i][j];//因为上面f[i][j]=f[i-1][j],所以l相当于前i-1个物品，j个容量
			f[i][j]=max(l,k);
		}
			
	}
	}
		cout<<f[N][V]<<endl;
		}
			
		
		
	}

状态变量：f[i] [j]表示前i件物品放入容量为j的背包的最大价值

当前容量为j，我们要考虑第i件物品能否放入？是否放入？

如果当前背包容量j<v[i],不能放入，则f[i] [j]=f[i-1] [j]
如果当前背包容量j>=v[i]，能放入但是要比较代价
如果第i件物品不放入背包，则f[i] [j]=f[i-1] [j]

如果第i件物品放入背包，则背包容量还剩j-v[i],所以要取前i-1件物品放入背包剩余容量j-v[i]所获得的最大价值f[i-1] [j-v[i]]。