java 代码

import java.util.Scanner;

public class Main {

    static int N = 1010;
    static int[] v = new int[N];    //物品体积
    static int[] w = new int[N];    //物品价值

    static int[] f = new int[N];//最大价值


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();   //物品个数
        int m = sc.nextInt();   //背包最大容量
        for (int i = 1; i <= n; i ++ ) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        //优化前
//        for (int i = 1; i <= n ; i ++ )
//            for (int j = 0; j <= m; j++ ) {
//                if (v[i] > j)   f[i][j] = f[i - 1][j]; //第i个物品大于背包体积 装不下 则不装
//                else {
//                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
//                }
//            }
        //优化后
        // 一维数组的原因：由于 i 之和 i - 1 有关系， 则可以滚动。
        // j从大到小的原因： f[j] = max(f[j], f[j - v[i]] + w[i]); f[j]的每次更新是需要上一层的f[j]
        // 比如 dp[8](i = 2) = max (dp[8](i = 1), dp[3](i = 1) + w[i])
        //如果从小到大更新 那么dp[8](i = 2) = max (dp[8](i = 2), dp[3](i = 2) + w[i])， 因为dp[3] 已经先被i=2时先更新过了
        //所以需要从大到小循环， 目的是为了让 dp[higher]用到 较小的索引值时，让dp[lower] 仍然是上一层的值
        for (int i = 1; i <= n ; i ++ )
            for (int j = m; j >= v[i]; j -- )
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
        System.out.println(f[m]);

    }
}