Knapsack 01

gistfile1.txt

/**
 * 最简单的01背包
 * N个物品，装入重量大小为M的包，每个物品重w[i]，价值p[i], 求包内最大价值
 * 输入规模 ：1<=N<=3402, 1<=M<=12880
 * 
 * 设f[i][j]是前i个物品装入重量大小为j的包的最大值,
 * f[i][j] = max{f[i-1][j], f[i-1][j-w[i]] + p[i]}
 * 最终结果是f[n-1][m]
 * 
 * 时间复杂度为O(N*M),空间复杂度为O(N*M),空间复杂度可以优化到O(N)
 * 
 * 因为f[i][j] 仅仅和f[i-1][j], f[i-1][j-w[i]]有关，所以肯定可以使用滚动数组优化空间，
 * 更巧的一个方法可以仅使用一维数组f[0..MAXN]来代替f[][], 但是需要逆序的来计算f[j] = max(f[j], f[j-w[i]]+p[i])
 * 
 * 初始化f[0][x] = 0, f[x][0] = 0 
 * 
 * Online judge : http://acm.hdu.edu.cn/showproblem.php?pid=2602
 */
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}
}
class Task {
	public void solve(int testNumber, InputReader in, PrintWriter out){
		int t = in.nextInt();
		while (t-- > 0){
			int n = in.nextInt(), v = in.nextInt();
			int[] p = readIntArray(in, n);
			int[] w = readIntArray(in, n);

			int[] f = new int[v+1];
			for (int i=0; i<n; i++)
				for (int j=v; j>=w[i]; j--)
					f[j] = Math.max(f[j], f[j-w[i]] + p[i]);
			out.println(f[v]);
		}
	}
	int[] readIntArray(InputReader in, int n){
		int[] array = new int[n];
		for (int i=0; i<n; i++)
			array[i] = in.nextInt();
		return array;
	}
}

class InputReader{
	public BufferedReader reader;
	public StringTokenizer tokenizer;
	
	public InputReader(InputStream stream){
		reader = new BufferedReader(new InputStreamReader(stream));
		tokenizer = null;
	}
	public String next(){
		while (tokenizer == null || !tokenizer.hasMoreTokens()){
			try{
				tokenizer = new StringTokenizer(reader.readLine());
			}catch(IOException e){
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	public int nextInt(){
		return Integer.parseInt(next());
	}
}