01背包问题

01背包问题

Created: Jun 23, 2021 8:02 PM

1. 问题描述

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

2. 暴力破解方法

  • 每件物品只有选和不选两种途径,可以使用回溯法搜索出所有的情况,然后取最大的值
  • 这样写非常慢,因为遍历了每个物品的取和不取的所有情况,时间复杂度为O(2^n)
class Solution {

    int result = 0;
  int cur = 0;
    public maxValue(int[] value, int[] weight, int w) {
        backTracking(value, weight, w, 0);
        return result;
    }

    private void backTracking(int[] value, int[] weight, int w, int startIndex) {

        if (startIndex > value.length - 1 || w < 0) {
            return;
        }

        for (int i = startIndex; i < value.length; i++) {
            cur += value[i];
            w -= weight[i];            
            result = Math.max(result, cur);
            backTracking(value, weight, w, i + 1);
            cur -= value[i];
            w += weight[i];
        }
    }
}

3. 二维dp数组01背包

因为每一步都是依托于上一步你的物品的取放的选择的,是一个可以用dp来做的类型题目~

我们需要做以下几步来思考整个逻辑

3.1 确定dp数组和下标的含义

  • 在二维数组里面,我们希望用dp[i][j] 表示我在做了对于前i个产品的选择,在容量为j的时候能够获得的最大的价值
  • 在这个定义下,那么最终我需要的值就是dp[n][W], 这就是我在做了n个关于这些产品的选取放弃的决定,在满足重量不超过W的限定条件下能取得的最大价值了

3.2 确定递推公式

// 不选i这件产品,容量为j的值; 还有选了i这件产品,那么i-1件产品的总重量需要满足 j - weight[i], 这个时候再加上i这件产品的价值,  这两个dp数组位置的最大值就是dp[i][j]需要取的值了
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])

3.3 如何初始化这个数组

  • 对于第一列 j = 0 意味着现在背包允许的重量为0,所以不管是哪个产品,有的价值都为0
  • 对于第一行 i = 0, 此时我们只能选择物品0,而且题目中说了只能最多拿一件产品,所以可以将这一行都声明为weight[0]

3.4 确定遍历顺序

先遍历物品,再遍历背包重量 其实均可

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 这个是为了展现dp数组里元素的变化
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

3.5 代码

public int WeightBagProblem(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]);
                }
            }
        }

                return dp[wLen][bagSize];
    }

4. 数组降维 — 利用滚动数组解决01背包问题

  • 在第三部分当中,我们的递归公式推导出来是:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
  • 如果在这里 我们将dp[i-1][]那一层的东西拷贝到dp[i]这一层,那么我们是可以使用一个一维数组来解决这个问题的

4.1 确定dp数组的定义

在一维dp数组当中, dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]

4.2 一维数组递推公式

dp[j] = max(dp[j], dp[j-weight[i]] + value[i])

4.3 一维数组初始化

  • 首先确定背包容量为0所背的物品的最大价值也为0
  • 假设所有产品价值非负,那么我们就不用初始化数组其他位置的值为负无穷了,保持为0即可

4.4 一维数组遍历顺序

or(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}
  • 不能正序遍历,因为正序的话物品会被重复加入很多次
    • 因为在遍历后一个的时候实际上已经用了前一个的结果
    • 譬如
      • dp[1] = dp[1 - weight[0]] + value[0]
      • dp[2] = dp[2 - weight[0]] + value[0]
      • dp[2] 会用到dp[1] (当weight[0] = 1的时候) 这个时候相当于我们把0号产品用了两次了 这是不能够的
public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWight = 4;
        testWeightBagProblem(weight, value, bagWight);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定义dp数组:dp[j]表示背包容量为j时,能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序:先遍历物品,再遍历背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp数组
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");
        }
    }

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 stone2paul@gmail.com

文章标题:01背包问题

文章字数:1.4k

本文作者:Leilei Chen

发布时间:2021-06-25, 09:20:17

最后更新:2021-06-25, 09:21:30

原始链接:https://www.llchen60.com/01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏