3533006_ac_844ms_5400k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {
	private Scanner in;

	public static void main(String [] args) {
		new Main().run();
	}

	private void run() {
		in = new Scanner (System.in);
		int cas;
		int n, weight;
		int [] max = new int [10000];
		int [] v = new int [500];
		int [] w = new int [500];

		cas = in.nextInt();
		while (cas-- > 0) {
			weight = -(in.nextInt() - in.nextInt());
			Arrays.fill(max, -1);
			max[0] = 0;
			n = in.nextInt();
			for (int i = 0; i < n; i++) {
				v[i] = in.nextInt();
				w[i] = in.nextInt();
			}
			for (int i = 0; i < weight; i++) {
				if (max[i] != -1) {
					for (int j = 0; j < n; j++) {
						int tmpw = w[j] + i;
						int tmpv = v[j] + max[i];
						if (tmpw <= weight && (max[tmpw] == -1 || max[tmpw] > tmpv)) {
							max[tmpw] = tmpv;
						}
					}
				}
			}
			if (max[weight] == -1) {
				System.out.println("This is impossible.");
			} else {
				System.out.println("The minimum amount of money in the piggy-bank is " + max[weight] + ".");
			}
		}
	}
}