题解 1924: 蓝桥杯算法提高VIP-01背包

参考代码:

import java.util.Scanner;

public class Main4 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 01背包问题
		Scanner scanner = new Scanner(System.in);
		int num = scanner.nextInt();// 物品數量
		int wight = scanner.nextInt();// 物品重量
		int[] v = new int[num + 1];// 价值
		int[] w = new int[num + 1];// 重量
		int[][] dp = new int[num + 1][wight + 1];// 行代表物品 列代表价值
		for (int i = 1; i <= num; i++) {
			w[i] = scanner.nextInt();
			v[i] = scanner.nextInt();
		}
		for (int i = 1; i <= num; i++) {
			for (int j = 1; j <= wight; j++) {
				if (j < w[i]) {
					dp[i][j] = dp[i - 1][j];
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]]
							+ v[i]);
				}
			}
		}
		System.out.println(dp[num][wight]);

	}

}