首页 > 试题广场 >

【模板】01背包

[编程题]【模板】01背包
  • 热度指数：24567 时间限制：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
牛客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)
提交观点

问题信息

难度：
2条回答 1985浏览

热门推荐

通过挑战的用户

查看代码

相关试题

【模板】01背包

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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