Java 代码

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        //创建输入流对象
        Scanner in = new Scanner(System.in);
        //输入物品的个数
        int N = in.nextInt();
        //输入背包的容积
        int V = in.nextInt();
        //创建一个长度为 N 的一维数组，用于存储每个物品的价值
        int[] v = new int[N + 1];
        //创建一个长度为 N 的一维数组，用于存储每个物品的体积
        int[] w = new int[N + 1];
        //输入每个物品的价值和体积
        for(int i = 1; i <= N; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        //关闭输入流
        in.close();
        System.out.println(solution(v, w, N, V));
    } 

    // opt[i][j]表示背包容积为 j 时，存放物品 i 时的最大价值。此时就要比较当前背包容积 j 与物品 i 的体积 va[i]，分为以下两种情况
    // (1）当 va[i] > j 时，背包肯定不能放不下物品 i，opt[i][j] = opt[i - 1][j]
    // (2) 当 va[i] <= j 时，有两种选择：放物品 i 和不放物品 i，由于是最大价值，故取两者最大值
    //    1) 放物品 i ，则opt[i][j] = wa[i] + opt[i-1][j-va[i]]
    //    2) 不放物品 i，则opt[i][j] = opt[i-1][j]
    //    3) 由于是求总价值最大，故取两者中的最大值
    // (3) opt[n][v] 即为所求
    public static int solution(int[] va, int[] wa, int n, int v){
        int[][] opt = new int[n + 1][v + 1];
        opt[0][0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= v; j++){
                if(j >= va[i]){
                    opt[i][j] = Math.max(opt[i-1][j-va[i]] + wa[i], opt[i-1][j]);
                }
                else{ // 当前背包剩余容积 j 小于当前第 i 种物品的体积
                    opt[i][j] = opt[i-1][j];
                }
            }
        }
        return opt[n][v];
    }
}