代码随想录算法训练营第42天 | 0-1背包理论基础, 416.分割等和子集

0-1背包理论基础

代码随想录链接-二维dp数组

代码随想录链接-一维dp数组

0-1背包问题指的是类如:

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

使用动态规划解决0-1背包问题时，主要有两种dp数组的形式：

二维dp数组

动态规划五部曲： * 确定dp数组及下标的含义

有一种写法, \(dp[i][j]\)表示从下标\([0-i]\)中的物品里任意取， 放进容量为\(j\)的背包, 价值总和最大值是多少.

• 确定递推公式

  \(dp[i][j]\)的确定取决于下面两种情况:

  • 物品\(i\)不放入, 此时\(dp[i][j] == dp[i-1][j]\), 背包的重量和价值与物品\(i\)无关.
  • 物品\(i\)放入, 此时的\(dp[i][j] == dp[i - 1][j - weight[i]] + value[i]\), 即背包容量为不含有当前物品时的最大价值加上本物品的价值

  所以递推公式有: \[dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])\]

• dp数组的初始化

  如果\(j\)为0时, 背包价值一定为0, 所以\(dp[i][0]\)要初始化为0, 如果\(i\)为0时, 在\(j\)大于\(value[0]\)时, 一定有\(dp[0][j] == 0\). 其余数字都是由这些推导出来, 初始化为0就好.

• 遍历顺序

  先遍历物品, 再遍历背包罢(代码随想录里有先遍历背包容量的, 二刷再记)

  // 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];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

• 举例推导

懒了

一维dp数组

对于一维dp数组来说, 同样有上面五步:

• 确定dp数组定义

  \(dp[j]\)表示容量为j的背包, 所背物品价值的最大值

• dp数组的递推公式

  同样也是放物品\(i\)与不放物品\(i\), 有\[dp[j] = max(dp[j], dp[j - weight[i]] + value[i])\]

• dp数组的初始化

  \(dp[0]\)一定初始化为0, 因为此时背包容量为0. 对于其他位置的值, 根据递推公式可知如果给定物品的价值都是正整数, 初始化为0即可.

• 遍历顺序

  先遍历物品, 再遍历背包容量

for(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]);
    }
}

注意这时候遍历背包容量的顺序与二维的不同, 要从大到小来遍历, 目的是为了保证物品\(i\)只被放入一次.

• 举例推导

  又懒了

416.分割等和子集

代码随想录链接

题目

LeetCode-416.分割等和子集

给定一个只包含正整数的飞空数组, 判断是否可以将其分割为两个等和子集.

自己的想法

那其实就是判断能否用里面的价值与重量相等的物品, 装到容量为sum / 2的背包里, 且装满时总和为sum / 2.

使用一维dp数组, 可以得到递推公式为\[dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])\]

题解

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        vector<int> dp(nums.size() * 100 + 1, 0); // 根据给定的信息来初始化数组
        for (int i = 0; i < nums.size(); i++)   // 求原数组之和
            sum += nums[i];
        if (sum % 2)    // 若和为奇数, 必不能满足条件
            return false;
        int target = sum / 2;
        for (int i = 0; i < nums.size(); i++)   // 先遍历物品, 再遍历重量
            for (int j = target; j >= nums[i]; j--)
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        if (dp[target] == target)   // 如果最后容量为sum / 2的位置上, 最多能装sum / 2价值的物品, 则满足条件
            return true;
        return false;
    }
};