题目描述

blablabla

JAVA 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    /**
     * 优秀文章
     * https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html#%E4%B8%80%E7%BB%B4dp%E6%95%B0%E7%BB%84-%E6%BB%9A%E5%8A%A8%E6%95%B0%E7%BB%84
     */

    /**
    * 二维下的状态定义f[i][j]是前 i件物品，背包容量 j下的最大价值。
    * 一维下，少了前 i件物品这个维度，我们的代码中决策到第 i件物品（循环到第i轮），
    * f[j]就是前i轮已经决策的物品且背包容量 j下的最大价值。
     */

    /**
     * 如果使用顺序，会先更新f[4],再更新f[7]，对于这个书包问题来讲，
     * 就是有可能，在更新f[4]的时候，已经把这次能加的物品加进来了，
     * 然后更新f[7]的时候，还有可能再加一次，所以必须使用逆序，
     * 保证，f[4]是没有加入新物品前，背包里的最优解。
     */


    static int N = 1010;
    static int[] p = new int[N];//p[j]定义：N件物品，背包容量j下的最优解。 //有N件物品，则需要N次决策，
    static int[] v = new int[N];
    static int[] w = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s[] = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);//物品数量
        int V = Integer.parseInt(s[1]);//背包容积
        for (int i = 1; i <= n; i++) {
            String ss[] = br.readLine().split(" ");
            v[i] = Integer.parseInt(ss[0]);
            w[i] = Integer.parseInt(ss[1]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= v[i]; j--) {
                //p[i][j] = p[i-1][j];
                // 优化前，不选
                //p[j] = p[j];        //自动成立

//                if(j >= v[i])
//                {
//                    //p[i][j] = Math.max(p[i][j],p[i-1][j-v[i]] + w[i]);优化前  //选
//                }
                p[j] = Math.max(p[j],p[j-v[i]]+w[i]);
                /**
                 * dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品 i
                 * 一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，
                 * dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
                 */
            }
        }
        System.out.println(p[V]);
    }
}