01背包问题_01背包问题测试数据

动态规划----01背包问题

package dplanqiao;

import java.util.Scanner;

public class Main_01背包 {
	static int[][] dp;
	static int[] w;//价值
	static int[] v;//体积
	// dp[i][j]的定义是 当一共i件产品 并且空间为 j时,此时能装的最大价值 
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();//数量
		int m = scanner.nextInt();//背包容积
		w = new int[n + 1];//当前价值
		v = new int[n + 1];//当前容积
		
		for (int i = 1; i <= n; i++) {
			v[i] = scanner.nextInt();
			w[i] = scanner.nextInt();
		}
		dp = new int[n + 1][m + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (j < v[i]) {
					dp[i][j] = dp[i - 1][j];//状态转移方程
				} else {//此时这个物品装得下，但是我可以选择装进背包，可以选择不装进背包（因为不装进去的最大价值可能更大！！！），
					dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);//状态转移方程
				}
			}
		}
		System.out.println(dp[n][m]);
	}
}
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
33

测试数据：
4 8
2 3 4 5
3 4 5 6
正确答案：
10
1
2
3
4
5
6

运行结果如下：