蓝桥杯算法提高VIP-01背包（java）

解题思路:

注意事项:
参考代码:

import java.util.Scanner;

public class P1924 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();//背包个数
		int m=sc.nextInt();//能装的重量
		int []wi=new int[n+1];
		int []vi=new int[n+1];
		for (int i = 1; i < n+1; i++) {//输入每个背包的重量和价值
			wi[i]=sc.nextInt();
			vi[i]=sc.nextInt();
		}
		int [][]arr=new int[n+1][m+1];//声明动态规划表.其中arr[i][j]对应于：当前有i个物品可选
		//并且当前背包的容量为j时，我们能得到的最大价值
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < m+1; j++) {
				if (wi[i]>j) {
					arr[i][j]=arr[i-1][j];// 包的容量比当前该物品体积小，装不下，此时的价值与前i-1个的价值是一样的
				}else {
					arr[i][j]=Math.max(arr[i-1][j-wi[i]]+vi[i],arr[i-1][j]);//还有足够的容量可以装当前该物品，
					//但装了当前物品也不一定达到当前最优价值，所以在装与不装之间选择最优的一个
				}
			}
		}
		System.out.println(arr[n][m]);
	}
}