本文出自：http://blog.csdn.net/svitter

题意：典型到不能再典型的01背包。给了我一遍AC的快感。

//============================================================================

// Name        : 2602.cpp

// Author      : vit

// Version     :

// Copyright   : Your copyright notice

// Description : Hello World in C++, Ansi-style

//============================================================================

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

#define max(a, b) a > b ? a : b

struct Bone{

	int val;

	int vol;

};

Bone b[1010];

int dp[1010];

void ace(){

	//work point

	int t;

	int i, j ,k;

	//num

	int n, v;

	cin >> t;

	while(t --){

		memset(dp, 0, sizeof(dp));

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

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

			scanf("%d", &b[i].val);

		}

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

			scanf("%d", &b[i].vol);

		}

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

			for(j = v; j >= b[i].vol; j--){

				dp[j] = max(dp[j], dp[j - b[i].vol] + b[i].val);

			}

		printf("%d\n", dp[v]);

	}

}

int main() {

	ace();

	return 0;

}