蓝桥杯算法提高VIP-01背包-题解（Java代码）

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int num = input.nextInt();
		int[] p = new int[n];
		int[] w = new int[n];
		
		for(int i = 0 ; i < n ; i++) {
			p[i] = input.nextInt();
			w[i] = input.nextInt();
		}
		
		
		int[][] dp = new int[num+1][p.length];
		
		for(int i = 0 ; i < p.length ; i++) 
			for(int j = 1 ; j <= num ; j++) 
				dp[j][i] = i==0? (p[i]<=j?w[i]:0) : (p[i]<=j ? ( w[i] + dp[j-p[i]][i-1] >= dp[j][i-1] ? w[i] + dp[j-p[i]][i-1] : dp[j][i-1] ) : dp[j][i-1]);
					
		
		System.out.println(dp[num][p.length-1]);
		
	}
}