首页 > 试题广场 >

【模板】01背包

[编程题]【模板】01背包
  • 热度指数：28061 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}你有一个背包，最大容量为 V。现有 n 件物品，第 i 件物品的体积为 v_i，价值为 w_i。研究人员提出以下两种装填方案：
{\hspace{20pt}}_\texttt{1.}\, 不要求装满背包，求能获得的最大总价值；
{\hspace{20pt}}_\texttt{2.}\, 要求最终恰好装满背包，求能获得的最大总价值。若不存在使背包恰好装满的装法，则答案记为 0。

输入描述:
\hspace{15pt}第一行输入两个整数 n 和 V\left(1\leqq n,V\leqq 10^3\right)，分别表示物品数量与背包容量。 
\hspace{15pt}此后 n 行，第 i 行输入两个整数 v_i, w_i\left(1\leqq v_i,w_i\leqq 10^3\right)，分别表示第 i 件物品的体积与价值。


输出描述:
\hspace{15pt}输出两行： 
{\hspace{20pt}}_\texttt{1.}\, 第一行输出方案 \texttt{1} 的答案； 
{\hspace{20pt}}_\texttt{2.}\, 第二行输出方案 \texttt{2} 的答案（若无解输出 0）。
示例1

输入

3 5
2 10
4 5
1 4

输出

14
9

说明

\hspace{15pt}在该组样例中： 
\hspace{23pt}\bullet\, 选择第 1、第 3 件物品即可获得最大价值 10+4=14（未装满）； 
\hspace{23pt}\bullet\, 选择第 2、第 3 件物品可使背包体积 4+1=5 恰好装满且价值最大，为 5+4=9。
示例2

输入

3 8
12 6
11 8
6 8

输出

8
0

说明

\hspace{15pt}装第三个物品时总价值最大但是不满，装满背包无解。

备注:
\hspace{15pt}要求 O(nV) 的时间复杂度，O(V) 空间复杂度。
算法知识视频讲解
添加回答
Java
Pluchon头像 Pluchon

首先是最开始的二维数组的代码

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int capacity;//背包容量
    static int count;//物品个数
    static int [] v;//体积
    static int [] w;//价值
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        count = in.nextInt();
        capacity = in.nextInt();
        v = new int[count+1];
        w = new int[count+1];
        //使用for循环精准读取count组物品数据，避免无限读取
        for(int sign = 1;sign <= count;sign++) {
            int a = in.nextInt();
            int b = in.nextInt();
            v[sign] = a;
            w[sign] = b;
        }
        //背包不满
        int ret1 = notFilled();
        //背包满
        int ret2 = filled();
        //打印结果
        System.out.println(ret1);
        System.out.println(ret2);
    }

    private static int notFilled(){
        //定义dp表，dp[i][j]表示从前i个物品中选取体积不超过j的最大价值，不能超过背包容量
        int [][] dp = new int[count+1][capacity+1];
        //填表
        for(int i = 1;i <= count;i++){
            //j表示当前考虑的背包容量（j），能否装得下第i个物品（v[i]）
            for(int j = 0;j <= capacity;j++){
                //挑选/不挑选i物品
                dp[i][j] = dp[i-1][j];//不挑选
                if(j >= v[i]){
                    //判断再决定是否挑选
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
                }
            }
        }
        return dp[count][capacity];
    }

    private static int filled(){
        //定义dp表，dp[i][j]表示从前i个物品中选取体积恰好为j的最大价值，同样也不能超过背包容量
        int [][] dp = new int[count+1][capacity+1];
        //初始化，由于不选择物品怎么样也达不到超过1的容量，初始化为-1
        for(int i = 1;i <= capacity;i++){
            dp[0][i] = -1;
        }
        //填表
        for(int i = 1;i <= count;i++){
            for(int j = 0;j <= capacity;j++){
                dp[i][j] = dp[i-1][j];//不挑选
                //如果选择i物品，要确保选i之前的空间里存在最大价值（不能为-1）
                //并且还要确保有足够位置
                if(j >= v[i] && dp[i-1][j-v[i]] != -1){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
                }
            }
        }
        //判断下是不是-1的情况
        return dp[count][capacity] == -1 ? 0 : dp[count][capacity];
    }
}

但是这样太占空间了，我们做下空间优化，变成一个一维数组就好，并且优化常数的时间复杂度

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int capacity;//背包容量
    static int count;//物品个数
    static int [] v;//体积
    static int [] w;//价值
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        count = in.nextInt();
        capacity = in.nextInt();
        v = new int[count+1];
        w = new int[count+1];
        //使用for循环精准读取count组物品数据，避免无限读取
        for(int sign = 1;sign <= count;sign++) {
            int a = in.nextInt();
            int b = in.nextInt();
            v[sign] = a;
            w[sign] = b;
        }
        //背包不满
        int ret1 = notFilled();
        //背包满
        int ret2 = filled();
        //打印结果
        System.out.println(ret1);
        System.out.println(ret2);
    }

    private static int notFilled(){
        //定义dp表，dp[j]表示从前i个物品中选取体积不超过j的最大价值，不能超过背包容量
        //滚动数组优化一：一维化
        int [] dp = new int[capacity+1];
        //填表
        for(int i = 1;i <= count;i++){
            //j表示当前考虑的背包容量（j），能否装得下第i个物品（v[i]）
            //滚动数组注意点：反向填表顺序
            //并且可以再做常数级别优化，遍历到了v[i]后就不用继续判断了，因为都不符合要求了，东西背包放不下
            for(int j = capacity;j >= v[i];j--){
                //挑选/不挑选i物品
                //滚动数组优化二：不用考虑不选的情况
                if(j >= v[i]){
                    //判断再决定是否挑选
                    dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
                }
            }
        }
        //滚动数组优化三：直接返回值
        return dp[capacity];
    }

    private static int filled(){
        //定义dp表，dp[i][j]表示从前i个物品中选取体积恰好为j的最大价值，同样也不能超过背包容量
        //滚动数组优化一：一维化
        int [] dp = new int[capacity+1];
        //初始化，由于不选择物品怎么样也达不到超过1的容量，初始化为-1
        for(int i = 1;i <= capacity;i++){
            dp[i] = -1;
        }
        //填表
        for(int i = 1;i <= count;i++){
            //滚动数组注意点：反向填表
            //并且可以再做常数级别优化，遍历到了v[i]后就不用继续判断了，因为都不符合要求了，东西背包放不下
            for(int j = capacity;j >= v[i];j--){
                //滚动数组优化二：不用考虑不选的情况
                //如果选择i物品，要确保选i之前的空间里存在最大价值（不能为-1）
                //并且还要确保有足够位置
                if(j >= v[i] && dp[j-v[i]] != -1){
                    dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
                }
            }
        }
        //判断下是不是-1的情况
        //滚动数组优化三：直接返回值
        return dp[capacity] == -1 ? 0 : dp[capacity];
    }
}
发表于 2026-01-13 16:10:46 回复(0)
Java
云淡_风轻头像 云淡_风轻 
//背包问题总结，4种，求最大价值，且回溯物品
//1、0-1必须装满
//2、0-1可不装满
//3、可重复使用-必须装满
//4、可重复使用-可不装满

import java.util.ArrayList;
import java.util.Arrays;

public class Backpack01 {
    public static void main(String[] args) {
        int n = 5;          // 物品数量
        int V = 19;          // 背包容量
        int[] v = {12, 11, 6, 7, 8};// 物品体积
        int[] w = {6, 8, 8, 7, 10};// 物品价值

        // 0-1背包刚好装满背包的最大价值
        solution1(n, V, v, w);

        // 0-1背包不要求装满背包最大价值
        solution2(n, V, v, w);

        // 物品可重复-刚好装满背包的最大价值
        solution3(n, V, v, w);

        // 物品可重复-不要求装满背包的最大价值
        solution4(n, V, v, w);

    }

    //0-1背包问题，要求装满背包，返回最大价值，且返回选了哪些物品的索引
    public static void solution1 (int n, int V, int[] v, int[] w) {
        if (n == 0 || V == 0 || v == null || w == null) {
            return;
        }
        if (v.length != w.length || v.length != n) {
            return;
        }
        int[] dp = new int[V + 1];
        int[] cur = new int[V + 1];
        Arrays.fill(dp, -1); // 初始化为-1，表示无法装满
        dp[0] = 0;           // 容量0刚好装满，价值0
        // 0-1背包核心循环（逆序遍历容量）
        for (int i = 0; i < n; i++) { // 遍历每个物品
            for (int j = V; j >= v[i]; j--) { // 逆序遍历容量
                // 更新dp2（要求刚好装满）
                if (dp[j - v[i]] != -1 && dp[j] < dp[j - v[i]] + w[i]) {
                    dp[j] = dp[j - v[i]] + w[i];
                    cur[j] = i;
                }
            }
        }
        if (dp[V] == -1) {
            System.out.println("无法装满背包");
        } else {
            System.out.println("刚好装满的最大价值：" + dp[V]);
            System.out.println("刚好装满的最大价值所选择的物品：");
            for (int i = V; i >= 1; ) {
                int index = cur[i] + 1;
                System.out.println("第" + index + "个物品【" + "体积：" + v[cur[i]] + "，价值：" + w[cur[i]] + "】");
                i = i - v[cur[i]];
            }
        }
    }

    //0-1背包问题，返回最大价值，不要求装满，且返回最后一个物品的索引
    public static void solution2 (int n, int V, int[] v, int[] w) {
        if (n == 0 || V == 0 || v == null || w == null) {
            return;
        }
        if (v.length != w.length || v.length != n) {
            return;
        }
        int[] dp = new int[V + 1];
        int[] used = new int[n];
        ArrayList<Integer> list = new ArrayList<>();
        int last = solution2(n, V, v, w, used, dp);
        list.add(last);
        used[last] = 1;
        System.out.println("\n不要求装满的最大价值：" + dp[V]);

        int sum = w[last];
        for (int i = V - v[last]; i >= 1 && sum < dp[V]; ) {
            last = solution2(n, i, v, w, used, new int[i + 1]);
            list.add(last);
            used[last] = 1;
            sum += w[last];
            i = i - v[last];
        }
        System.out.println("不要求装满的最大价值所选择的物品：");
        for (Integer integer : list) {
            int index = integer + 1;
            System.out.println("第" + index + "个物品【" + "体积：" + v[integer] + "，价值：" + w[integer] + "】");
        }
    }
    private static int solution2(int n, int V, int[] v, int[] w, int[] used, int[] dp) {
        Arrays.fill(dp, 0);
        // 0-1背包核心循环（逆序遍历容量）
        int cur = 0;
        for (int i = 0; i < n; i++) { // 遍历每个物品
            if (used[i] == 1) {
                continue;
            }
            for (int j = V; j >= v[i]; j--) { // 逆序遍历容量
                // 更新dp1（不要求装满）
                if (dp[j] < dp[j - v[i]] + w[i]) {
                    dp[j] = dp[j - v[i]] + w[i];
                    cur = i;
                }
            }
        }
        return cur;
    }

    // 可重复使用物品，刚好装满背包
    public static void solution3 (int n, int V, int[] v, int[] w) {
        if (n == 0 || V == 0 || v == null || w == null) {
            return;
        }
        if (v.length != w.length || v.length != n) {
            return;
        }
        int[] dp = new int[V + 1];
        int[] last = new int[V + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 1; i <= V; i++) {
            for (int j = 0; j < n; j++) {
                if (i < v[j]) {
                    continue;
                }
                if (dp[i - v[j]] != -1 && dp[i] < dp[i - v[j]] + w[j]) {
                    dp[i] = dp[i - v[j]] + w[j];
                    last[i] = j;
                }
            }
        }
        if (dp[V] == -1) {
            System.out.println("\n物品可重复-无法装满背包");
        } else {
            System.out.println("\n物品可重复-刚好装满的最大价值：" + dp[V]);
            System.out.println("物品可重复-刚好装满的最大价值所选择的物品：");
            for (int i = V; i >= 1; ) {
                int index = last[i] + 1;
                System.out.println("第" + index + "种物品【" + "体积：" + v[last[i]] + "，价值：" + w[last[i]] + "】");
                i = i - v[last[i]];
            }
        }
    }

    // 可重复使用物品，不要求装满背包
    public static void solution4 (int n, int V, int[] v, int[] w) {
        if (n == 0 || V == 0 || v == null || w == null) {
            return;
        }
        if (v.length != w.length || v.length != n) {
            return;
        }
        int[] dp = new int[V + 1];
        int[] last = new int[V + 1];
        Arrays.fill(last, -1);
        for (int i = 1; i <= V; i++) {
            for (int j = 0; j < n; j++) {
                if (i < v[j]) {
                    continue;
                }
                if (dp[i] < dp[i - v[j]] + w[j]) {
                    dp[i] = dp[i - v[j]] + w[j];
                    last[i] = j;
                }
            }
        }
        System.out.println("\n物品可重复-不要求装满的最大价值：" + dp[V]);
        System.out.println("物品可重复-不要求装满的最大价值所选择的物品：");
        for (int i = V; i >= 1; ) {
            if (last[i] == -1) {
                break;
            }
            int index = last[i] + 1;
            System.out.println("第" + index + "种物品【" + "体积：" + v[last[i]] + "，价值：" + w[last[i]] + "】");
            i = i - v[last[i]];
        }
    }
}


//输出结果
刚好装满的最大价值：18
刚好装满的最大价值所选择的物品：
第5个物品【体积：8，价值：10】
第2个物品【体积：11，价值：8】

不要求装满的最大价值：18
不要求装满的最大价值所选择的物品：
第5个物品【体积：8，价值：10】
第3个物品【体积：6，价值：8】

物品可重复-刚好装满的最大价值：23
物品可重复-刚好装满的最大价值所选择的物品：
第3种物品【体积：6，价值：8】
第3种物品【体积：6，价值：8】
第4种物品【体积：7，价值：7】

物品可重复-不要求装满的最大价值：24
物品可重复-不要求装满的最大价值所选择的物品：
第3种物品【体积：6，价值：8】
第3种物品【体积：6，价值：8】
第3种物品【体积：6，价值：8】

发表于 2025-12-04 15:37:49 回复(0)
Java
BraveCoder头像 BraveCoder 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 物品数量
        int V = sc.nextInt(); // 背包最大容量
        int[] v = new int[n + 1]; // 物品体积（1-based索引）
        int[] w = new int[n + 1]; // 物品价值（1-based索引）

        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        // 1. 方案1：不要求装满背包，求最大价值
        int maxUnfilled = solveUnfilled(n, V, v, w);
        // 2. 方案2：要求恰好装满背包，求最大价值（无解输出0）
        int maxFilled = solveFilled(n, V, v, w);

        System.out.println(maxUnfilled);
        System.out.println(maxFilled);
        sc.close();
    }

    /**
     * 不要求装满背包的最大价值
     * 初始状态：dp[0...V] = 0（空背包价值为0，未装满也可从0开始累积）
     */
    private static int solveUnfilled(int n, int V, int[] v, int[] w) {
        int[] dp = new int[V + 1];
        // 遍历每个物品
        for (int i = 1; i <= n; i++) {
            // 倒序遍历容量（避免重复选同一物品）
            for (int j = V; j >= v[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        return dp[V];
    }

    /**
     * 要求恰好装满背包的最大价值
     * 初始状态：dp[0] = 0（容量0恰好装满时价值为0），dp[1...V] = -∞（初始标记为无法装满）
     */
    private static int solveFilled(int n, int V, int[] v, int[] w) {
        int[] dp = new int[V + 1];
        // 初始化：除容量0外，其余均设为负无穷（表示无法装满）
        for (int j = 1; j <= V; j++) {
            dp[j] = Integer.MIN_VALUE;
        }

        // 遍历每个物品
        for (int i = 1; i <= n; i++) {
            // 倒序遍历容量
            for (int j = V; j >= v[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        // 若最终容量V仍为负无穷，说明无法装满，返回0；否则返回dp[V]
        return dp[V] < 0 ? 0 : dp[V];
    }
}

发表于 2025-09-26 15:49:46 回复(0)
Java
牛客391767071号头像 牛客391767071号
    /**
     *  背包问题/装箱问题           【动态规划DP】
     *  【原问题】f(n,V)：有n个物品(有各自的体积和价值)，一个容量为V的背包，最大装入价值(最大装入体积)是多少？
     *
     *  【算法一】：动态规划DP/自底向上     //本题适合【算法一】，因为【子问题之间：可能存在重叠/重复计算】。
     *  【算法二】：降维递归/自顶向下
     *  【降维】：
     *      1.【降维思路】【2种降维思路之一】：直接对原问题/输入数据/数组 进行降维处理；
     *      2.【降维处理】去掉第n个物品(最后一个物品)进行降维。子问题：前n-1个物品对应的多个子问题。
     *      3.【降维关系分析/父子问题关系分析】：
     *          a. 去掉的第n个物品，其体积itemVolumes[n-1]>容量V，即无法装入容器/背包，则【降维关系】为：
     *              f(n,V) = f(n-1,V)
     *          b. 去掉的第n个物品，其体积itemVolumes[n-1]<=容量V，即能够装入容器/背包；
     *             此时有2种选择方案：选择装入该物品、选择不装入该物品；
     *             由于2种方案都有可能产生“全局最优解”，所以需要比较2种方案的解，以得到最优解。
     *             此时，【降维关系】为：
     *              f(n,V) = max{f(n-1,V-itemVolumes[n-1])+itemValues[n-1], f(n-1,V)}
     *          c. 可以发现父问题f(n,V)，依赖2个子问题：
     *             前n-1个物品对应的2个子问题：f(n-1,V)、f(n-1,V-itemVolumes[n-1])。
     *             【子问题之间：可能存在重叠/重复计算】：
     *                  例如当第n和n-1物品体积都为3时，上2个子问题都依赖f(n-2,V-3)。
     *          d. 发现“原问题/子问题”由“n和V”2个参数共同定义，所以子问题的个数将是 n*V 个。
     *             所以：如果要暂存子问题的解，应该使用二维数组/矩阵：dp[n][V](不加额外行列时)。
     *            
     *  【降维关系/计算规则/状态转移方程】：
     *      1. 第n个物品，其体积itemVolumes[n-1]>容量V，即无法装入容器/背包，则【降维关系】为：
     *          f(n,V) = f(n-1,V)
     *      2. 第n个物品，其体积itemVolumes[n-1]<=容量V，即能够装入容器/背包，则【降维关系】为：
     *          f(n,V) = max{f(n-1,V-itemVolumes[n-1])+itemValues[n-1], f(n-1,V)}
     *
     *  【动态规划DP算法】中间结果集/二维矩阵dp[n+1][V+1](加额外行列时):
     *      1. dp[i][j]：保存子问题f(i,j)的解，即：
     *                  前i个物品装入容量为j的容器/背包时，最大装入价值/最大装入体积/最大装入个数。
     *         (dp[i][j]：前i个物体放在V中的最大价值/体积是多少。)
     *
     *
     *  @param volume       容器容量/背包体积/箱子体积  v
     *  @param n            物品个数
     *  @param itemVolumes  物品体积
     *  @param itemValues   物品价值（物品价值/物品体积/数量1）
     *  @return             最大装入价值（最大装入体积/最大装入个数）
     */
    public static int maxXBackPackAlgo(int volume, int n, int[] itemVolumes, int[] itemValues) {

        //x1. 定义：中间结果集/二维矩阵dp[n+1][V+1](加额外行列时):
        int V=volume;
        int[][] dp = new int[n+1][V+1];

        //x2. 计算：中间结果集/二维矩阵dp
        //dp[i][j]：保存子问题f(i,j)的解，即：前i个物品装入容量为j的容器/背包时，最大装入价值
        for(int i=0;i<=n;i++){
            for(int j=0;j<=V;j++){
                //x21. 额外行列初始化
                if(i==0 || j==0){
                    dp[i][j] = 0;
                    continue;
                }
                //x22. 边界计算/无法继续降维问题直接计算
                //无
                //x23. 统一降维计算：
                //【降维关系/计算规则/状态转移方程】：见前面。
                else{
                    if(itemVolumes[i-1] > j) {
                        dp[i][j] = dp[i-1][j];
                    }
                    else {
                        dp[i][j] = Math.max(dp[i-1][j-itemVolumes[i-1]] + itemValues[i-1] , dp[i-1][j]);
                    }
                }
            }
        }

        //x3. 返回结果：最大装入价值（最大装入体积/最大装入个数）
        return dp[n][V];
    }

   
    /**
     *  背包问题/装箱问题（恰好装满时最大装入价值）           【动态规划DP】
     *  【原问题】f(n,V)：有n个物品(有各自的体积和价值)，一个容量为V的背包，恰好装满时，最大装入价值(最大装入体积)是多少？
     *
     *  【算法一】：动态规划DP/自底向上     //本题适合【算法一】，因为【子问题之间：可能存在重叠/重复计算】。
     *      【与正常背包问题的区别】：见下面，共2处。
     *
     *  【降维关系/计算规则/状态转移方程】：
     *      1. 第n个物品，其体积itemVolumes[n-1]>容量V，即无法装入容器/背包，则【降维关系】为：
     *          f(n,V) = f(n-1,V)
     *      2. 第n个物品，其体积itemVolumes[n-1]<=容量V，即能够装入容器/背包，则【降维关系】为：
     *          f(n,V) = max{f(n-1,V-itemVolumes[n-1])+itemValues[n-1], f(n-1,V)}
     *         【与正常背包问题的区别】：子问题无解时，依赖子问题的方案/父问题 也无解。
     *
     *  【动态规划DP算法】中间结果集/二维矩阵dp[n+1][V+1](加额外行列时):
     *      1. dp[i][j]：保存子问题f(i,j)的解，即：
     *                 前i个物品装入容量为j的容器/背包时，恰好装满时，最大装入价值/最大装入体积/最大装入个数。
     *         【与正常背包问题的区别】：当无解时，即不能完全装满时，取值-1。注意额外行列初始化，区分是否装满。
     *
     *
     *  @param volume       容器容量/背包体积/箱子体积  v
     *  @param n            物品个数
     *  @param itemVolumes  物品体积
     *  @param itemValues   物品价值（物品价值/物品体积/数量1）
     *  @return             最大装入价值（最大装入体积/最大装入个数）；无解时，返回-1
     */
    public static int maxXFullBackPackAlgo(int volume, int n, int[] itemVolumes, int[] itemValues) {

        //x1. 定义：中间结果集/二维矩阵dp[n+1][V+1](加额外行列时):
        int V=volume;
        int[][] dp = new int[n+1][V+1];

        //x2. 计算：中间结果集/二维矩阵dp
        //dp[i][j]：保存子问题f(i,j)的解，即：前i个物品装入容量为j的容器/背包时，恰好装满时，最大装入价值
        //【与正常背包问题的区别】：当无解时，即不能完全装满时，取值-1。注意额外行列初始化，区分是否装满。
        for(int i=0;i<=n;i++){
            for(int j=0;j<=V;j++){
                //x21. 额外行列初始化
                //注意额外行列初始化，区分是否装满。
                if(j==0){           //第一列：都是 恰好装满。
                    dp[i][j] = 0;
                    continue;
                }
                else if(i==0 && j!=0){  //第一行(除第一个外)：都是无解， 不能完全装满，取值-1。
                    dp[i][j] = -1;
                    continue;
                }
                //x22. 边界计算/无法继续降维问题直接计算
                //无
                //x23. 统一降维计算：
                //【降维关系/计算规则/状态转移方程】：见前面。
                else{
                    if(itemVolumes[i-1] > j) {
                        dp[i][j] = dp[i-1][j];
                    }
                    else {
                        //【与正常背包问题的区别】：子问题无解时，依赖子问题的方案/父问题 也无解。
                        if(dp[i-1][j-itemVolumes[i-1]] != -1) {
                            dp[i][j] = Math.max(dp[i-1][j-itemVolumes[i-1]] + itemValues[i-1] , dp[i-1][j]);
                        } else {
                            dp[i][j] = dp[i-1][j];
                        }
                    }
                }
            }
        }

        //x3. 返回结果：恰好装满时，最大装入价值（最大装入体积/最大装入个数）
        return dp[n][V];
    }
发表于 2025-03-10 10:28:54 回复(0)
Java
想润的我反对画饼头像 想润的我反对画饼
import java.util.*;
public class  Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int bag = sc.nextInt();
        int[][] gift = new int[num][2];
        for (int i = 0; i < num; i++) {
            gift[i][0] = sc.nextInt();
            gift[i][1] = sc.nextInt();
        }
        System.out.println(getMaxValue(gift, bag));
        System.out.println(getfullbag(gift,bag));
    }
    private static int getMaxValue(int[][] gift, int bag ) {
        int[][] dp = new int[gift.length + 1][bag + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1 ; j < dp[0].length; j++) {
                if (j - gift[i - 1][0] >= 0 ) {
                    dp[i][j] = Math.max(dp[i - 1][j - gift[i - 1][0]] + gift[i - 1][1],
                                        dp[i - 1][j]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[gift.length][bag];
    }
    private static int getfullbag(int[][] gift, int bag) {
        int[][] dp = new int[gift.length + 1][bag + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1 ; j < dp[0].length; j++) {
                int left = j - gift[i - 1][0] ;
                if (left >= 0 ) {
                    if(left > 0){
                        if(dp[i-1][left] == 0){
                            dp[i][j] = dp[i-1][j];
                        }else{
                            dp[i][j] = Math.max(dp[i - 1][j - gift[i - 1][0]] + gift[i - 1][1],dp[i - 1][j]);
                        }
                    }else{
                        dp[i][j] = Math.max(gift[i - 1][1],dp[i - 1][j]);
                    }
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[gift.length][bag];
    }
}
发表于 2022-05-23 15:18:07 回复(0)
提交观点

问题信息

难度：
6条回答 2867浏览

热门推荐

通过挑战的用户

查看代码

相关试题

【模板】01背包

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号