写点什么

头脑风暴:完全背包

  • 2022 年 8 月 04 日
  • 本文字数:884 字

    阅读完需:约 3 分钟

头脑风暴:完全背包

题目

有 N 件物品和一个最多能背重量为 W 的背包。第 i 件物品的重量是 weight[i],得到的价值是 value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。

解题思路

完全背包和 01 背包问题唯一不同的地方就是,每种物品有无限件, 问背包能背的物品最大价值是多少? 求解该题与 01 背包问题的区别就在于遍历顺序上。


所以第一步确定 dp 数组的定义,在一维 dp 数组中,dp[j]表示:容量为 j 的背包,所背的物品价值可以最大为 dp[j]。


第二步确定递推公式,dp[j]可以通过 dp[j - weight[i]]推导出来,dp[j - weight[i]]表示容量为 j - weight[i]的背包所背的最大价值。dp[j - weight[i]] + value[i] 表示 容量为 j - 物品 i 重量 的背包 加上 物品 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]);


第三步 dp 数组初始化,由于物品价值都是大于 0 的,所以 dp 数组初始化的时候,都初始为 0 就可以了。


我们知道 01 背包内嵌的循环是从大到小遍历,为了保证每个物品仅被添加一次。


而完全背包的物品是可以添加多次的,所以要从小到大去遍历,代码如下:


// 先遍历物品,再遍历背包for(int i = 0; i < weight.size(); i++) { // 遍历物品    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}}
复制代码

代码实现

private static void testCompletePack(){    int[] weight = {1, 3, 4};    int[] value = {15, 20, 30};    int bagWeight = 4;    int[] dp = new int[bagWeight + 1];    for (int i = 0; i < weight.length; i++){ // 遍历物品        for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);        }    }    for (int maxValue : dp){        System.out.println(maxValue + "   ");    }}
复制代码


发布于: 刚刚阅读数: 4
用户头像

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

评论

发布
暂无评论
头脑风暴:完全背包_8月月更_HelloWorld杰少_InfoQ写作社区