首页 > 试题广场 >

【模板】01背包

[编程题]【模板】01背包
  • 热度指数：23698 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为v_i ,价值为w_i。

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述:
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数v_i和w_i，表示第i个物品的体积和价值。




输出描述:
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1

输入

3 5
2 10
4 5
1 4

输出

14
9

说明

装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。
示例2

输入

3 8
12 6
11 8
6 8

输出

8
0

说明

装第三个物品时总价值最大但是不满，装满背包无解。

备注:
要求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条回答 1845浏览

热门推荐

通过挑战的用户

查看代码

相关试题

【模板】01背包

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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