LeetCode_118_WeightBag

LeetCode

发布日期: 2022-06-19

更新日期: 2022-06-20

文章字数: 1.6k

阅读时长: 6 分

阅读次数:

本题不是LeetCode中的题目，仅仅是为了记录01背包问题基础知识。

1. question: 01背包问题（简单）

本篇是基础知识介绍，在LeetCode中并没有本题。

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

这种问题和贪心算法不同的是，本题中限制了每件物品只能用一次。

采用递归步骤。

定义数组dp[i][j], 表示从下标为[0-i]的物品里任意选择（注意，每类物品最多选一个），
放进容量为j的背包中，最大的价值总和。如下所示

那么显然，dp[i][j]的最大值，要么是dp[i-1][j]，也就是放不下物品i; 要么是dp[i-1][j-weight[i]] + value[j]，即放下一个物品i，其余空间选最优的。

本质上说，就是是否选取本元素，如果选取，那么占用一定的空间，其余空间一定要是最优结果；如果不选取，那么就是从[i-1]中选取元素，并且尽可能地占满空间j，即dp[i-1][j]最优。

因此，从动态规划的角度来看，当前最优结果取决于前面的结果。可利用递推公式进行计算。

感觉和不同路径有点类似。（题解中提到了可以从二维数组的两个方向遍历都可）

2. answers

这道题初次做还是比较难的。（理解地不是很透彻，先稍微放放）

从遍历的角度来看，一个比较简单的想法是：逐个将物品加入背包，计算value值，但是如果空间不够了，此时就需要从空间中拿出一个物品，换上本物品，重新计算value值，取最大值。

那么怎么保证拿出来的那个物品就是最应该拿出来的呢？而不是拿出其他物品？此时似乎可以暴力法，更准确一点的说，是回溯法，如果超出了空间就回溯。

从动态规划的角度来看，本次放入物品，取决于前面放入的物品以及容量。似乎可以保存，前面每时每刻的容量以及value值。这样，在放入本次物品时，如果容量足够，那么肯定放入；如果容量不够，此时就需要判断是否必须放入本物品了，回退到前面容量够的位置value + 本value（本情况和上面容量足够的情况在代码上可以统一，即均回退到容量足够的情况），并与上一次放入后的value进行比较，判断哪个大。

因此，需要设置二维数组，保存前面的每种情况。也就是说，每个值都是当前容量在当前物品即以前物品时的最优解。

代码如下所示：

public class Solution_0118 {

    public int testweightbagproblem(int[] weight, int[] value, int bagsize){

        // 定义保存结果的数组
        int[][] result = new int[weight.length][bagsize + 1];

        // 初始化数组
        // 对于result[0][j]的元素，只要 j >= weight[0]，就将其赋值为value[0]，因为可以存放。
        for (int i = 0; i < bagsize + 1; i++) {
            if(i >= weight[0]) result[0][i] = value[0];
        }

        // 对于result[i][0]，因为背包尺寸为0，显然将其赋值为0
        for (int i = 0; i < weight.length; i++) {
            result[i][0] = 0;
        }

        // 遍历数组，计算最优值，因为已经初始化了，所以直接从[1,1]开始遍历
        // 逐层遍历，即逐物品遍历
        for (int i = 1; i < weight.length; i++) {

            // 对每种背包尺寸情况计算。
            for (int j = 1; j < bagsize + 1; j++) {

                if(j - weight[i] >= 0)
                    result[i][j] = Math.max(result[i-1][j], result[i-1][j-weight[i]] + value[i]);
                else
                    result[i][j] = result[i-1][j];
            }
        }

        return result[weight.length - 1][bagsize];
    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0118 s = new Solution_0118();

        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagsize = 4;

        System.out.println(s.testweightbagproblem(weight, value, bagsize));
    }
}

可以看到，即使是二维数组，但是使用到的数据仅仅是上一层的数据，并没有使用所有的数据。即result[i-1][j]和result[i-1][j-weight[i]]，那么可不可以用一维数组来保存呢？后续在形成当前元素的值后，对其进行更新即可。

设置数组dp[j]表示上一个元素，在所有背包容量下的value最大值。此时遍历当前元素的时候，根据dp[j]来计算即可。

但是还有一个重要问题，我们计算当前dp[j]的时候，会用到dp[j-x]，如果按照从小打到的背包尺寸遍历的话，那么此时的dp[j-x]一定是当前元素下的情况，此时就不正确了，当前元素有可能选取两次。

怎么保证在计算dp[j]时，dp[j-x]没有被更新呢？显然需要从后向前遍历。这样就保证了小于j的所有尺寸均没有被更新。代码如下所示：

public int testweightbagproblem(int[] weight, int[] value, int bagsize){

    // dp[i] 表示上一个元素及其之前元素在所有背包尺寸下的最大值
    int[] dp = new int[bagsize + 1];

    int sums = 0;

    // 初始化第0个元素的选取，如果容量够，那么就放置第0个元素
    for (int i = 0; i < bagsize + 1; i++) {
        if(weight[0] <= i) dp[i] = value[0];
    }

    // 从第一个元素开始遍历
    for (int i = 1; i < weight.length; i++) {

        // 从第一个容量开始遍历
        // 注意，要从后向前遍历，这样，保证每个元素用到的状态都是前一个元素的状态
        for (int j = dp.length - 1; j > 0; j--) {

            // 更新当前元素的所有状态（当前值是前一个元素的）
            // 如果当前元素大于背包容量，显然当前元素仍然是上一个元素的状态，即dp[i][j] = dp[i-1][j]
            if(weight[i] > j) dp[j] = dp[j];

            // 如果可以装当前元素，那么就比较是否应该装，即dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i])
            else dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    return dp[bagsize];
}