有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。

第 ii 件物品的体积是 vivi，价值是 wiwi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，VN，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 NN 行，每行两个整数 vi,wivi,wi，用空格隔开，分别表示第 ii 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

题解

import java.util.Scanner;

public class o1bagClass {
    public static int o1bagSolution(int[] weight, int[] value, int bagWeight) {
        int num = weight.length;
        int[][] dp = new int[num + 1][bagWeight + 1];

        for (int i = 1; i <= num; i++) {
            for (int j = 0; j <= bagWeight; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= weight[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }

            }

        }
        /**
         * 以下注释段可以打印矩阵
         */
//        for (int[] ints : dp) {
//            for (int j = 0; j < dp[num].length; j++) {
//                System.out.print(ints[j] + " ");
//            }
//            System.out.println();
//        }

        return dp[num][bagWeight];
    }

    public static int o1bagSolutionOptimization(int[] weight, int[] value, int bagWeight) {
        int num = weight.length;
        int[] dp = new int[bagWeight + 1];
        dp[0] = 0;
        for (int i = 1; i <= num; i++) {
            for (int j = bagWeight; j >= 1; j--) {
                if (j >= weight[i - 1]) {
                    dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
                }
            }
        }


        return dp[bagWeight];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int itemsNumber = sc.nextInt();
        int bagWeight = sc.nextInt();
        int[][] arr = new int[itemsNumber][2];
        int[] weight = new int[itemsNumber];
        int[] value = new int[itemsNumber];
        for(int i = 0; i < itemsNumber; i++) {
            for(int j = 0; j < 2; j++) {
                arr[i][j] = sc.nextInt();
            }
            weight[i] = arr[i][0];
            value[i]=   arr[i][1];
        }
        System.out.println(o1bagSolutionOptimization(weight, value, bagWeight));
    }


}