写点什么

关于 01 背包问题

  • 2022 年 8 月 02 日
  • 本文字数:1205 字

    阅读完需:约 4 分钟

关于 01 背包问题

题目

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i],得到的价值是 value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

解题思路

本题可以采用动态规划的方式来求解,首先第一步就是线确定 dp 数组。


我们用 dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为 j 的背包,价值总和最大是多少。那么可以有俩种方式来推导出 dp[i][j],即不在背包中放物品 i 和在背包中放物品 i。


  • 不放物品 i: 由 dp[i - 1][j]推出,即背包容量为 j,里面不放物品 i 时的最大价值,其实就是当物品 i 的重量大于背包 j 的重量时,物品 i 无法放进背包中,此时 dp[i][j]就是 dp[i - 1][j],所以被背包内的价值依然和前面相同。

  • 放物品 i: 由 dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为 j - weight[i]的时候不放物品 i 的最大价值,那么 dp[i - 1][j - weight[i]] + value[i] ,就是背包放物品 i 得到的最大价值。


接下来初始化 dp 数组:


当 j < weight[0]的时候,dp[0][j] 应该是 0,因为背包容量比编号 0 的物品重量还小;当 j >= weight[0]时,dp[0][j] 应该是 value[0],因为背包容量放足够放编号 0 物品。所以初始化的代码为:


for (int j = weight[0]; j <= bagweight; j++) {    dp[0][j] = value[0];}
复制代码


然后确定便利顺序,本题先遍历物品还是先遍历背包都是可以的,代码如下:


// weight数组的大小 就是物品个数for(int j = 0; j <= bagweight; j++) { // 遍历背包容量    for(int i = 1; i < weight.size(); i++) { // 遍历物品        if (j < weight[i]) dp[i][j] = dp[i - 1][j];        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);    }}
复制代码

代码实现

public static void testweightbagproblem(int[] weight, int[] value, int bagsize){        int wlen = weight.length, value0 = 0;        //定义dp数组:dp[i][j]表示背包容量为j时,前i个物品能获得的最大价值        int[][] dp = new int[wlen + 1][bagsize + 1];        //初始化:背包容量为0时,能获得的价值都为0        for (int i = 0; i <= wlen; i++){            dp[i][0] = value0;        }        //遍历顺序:先遍历物品,再遍历背包容量        for (int i = 1; i <= wlen; i++){            for (int j = 1; j <= bagsize; j++){                if (j < weight[i - 1]){                    dp[i][j] = dp[i - 1][j];                }else{                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);                }            }        }        //打印dp数组        for (int i = 0; i <= wlen; i++){            for (int j = 0; j <= bagsize; j++){                System.out.print(dp[i][j] + " ");            }            System.out.print("\n");        }    }
复制代码


发布于: 18 小时前阅读数: 5
用户头像

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

评论

发布
暂无评论
关于 01 背包问题_8月月更_HelloWorld杰少_InfoQ写作社区