01背包(Java代码)

解题思路: 用动态规划算法
参考代码:

import java.util.Scanner;

public class 背包02 {

	public static void main(String[] args) {
		// 给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
		// 输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。
		// 以后N行每行两个数Wi和Vi,表示物品的重量和价值
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 物品个数
		int m = sc.nextInt(); // 背包能装的重量
		
		int[] w = new int[n]; // 背包中每个物品的重量
		int[] val = new int [n];  // 背包中每个物品的价值
		
		for (int i = 0; i < n; i++) {
			w[i] = sc.nextInt();
			val[i] = sc.nextInt();
		}
		
		int[][] v = new int [n+1][m+1]; // 加1表示第一行和第一列都要是0
		
		// 动态规划
		for (int i = 1; i < v.length; i++) { // 从1开始表示不处理第一行和第一列
			for (int j = 1; j < v[0].length; j++) {
				if(w[i-1] > j) { // 如果商品大于当前的承重那么就等于正上方单元格的值(不会描述，随便理解理解)
					v[i][j] = v[i-1][j];
				}else if(j >= w[i-1]) { // 如果还有多余的容量就选一个最大值(也是不会描述)
					v[i][j] = Math.max(v[i-1][j], val[i-1] + v[i-1][j-w[i-1]]);
				}
			}
		}
		
		// 用来看表格的
//		for (int i = 0; i < v.length; i++) {
//			for (int j = 0; j < v[i].length; j++) {
//				System.out.print(v[i][j] + " ");
//			}
//			System.out.println();
//		}
		
		System.out.println(v[n][m]);
		
	}

}

上面的看不清楚 附上一个无注释版

import java.util.Scanner;

public class 背包02 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int[] w = new int[n];
		int[] val = new int [n];
		
		for (int i = 0; i < n; i++) {
			w[i] = sc.nextInt();
			val[i] = sc.nextInt();
		}
		
		int[][] v = new int [n+1][m+1];
		
		for (int i = 1; i < v.length; i++) {
			for (int j = 1; j < v[0].length; j++) {
				if(w[i-1] > j) {
					v[i][j] = v[i-1][j];
				}else if(j >= w[i-1]) {
					v[i][j] = Math.max(v[i-1][j], val[i-1] + v[i-1][j-w[i-1]]);
				}
			}
		}
		
		System.out.println(v[n][m]);
		
	}

}