01背包问题

数据结构与算法 01背包

创建时间:2021-06-25 09:20

字数:1.4k 阅读:

评论:

01背包问题
1. 问题描述
2. 暴力破解方法
3. 二维dp数组01背包
4. 数组降维 — 利用滚动数组解决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