代码随想录算法训练营第三十四天 | leetcode：背包问题二维解法,背包问题一维解法,分割等和子集

_zzh 的个人博客 / 14 / 0 / 创建于 1个月前 / 更新于 1个月前

背包理论基础 01背包二维解法

问题

本题leetcode没有原题，是一道拟定的01背包题：给定一个 容量为4 的背包，问在以下物品当中，每件物品只能用一次,能装入的最大价值是多少？
物品为：
weight = [1, 3, 4];
value = [15, 20, 30];

物品	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

解题方法

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
确定递推公式：
再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
那么可以有两个方向推出来dp[i][j]：

不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

其中weight[i]]为当前物品i的重量。
[j - weight[i]]为背包减去当前物品i的重量，也就是装入上一次物品时背包的容量状态。
而dp[i - 1]为选择的上一次物品，所以dp[i - 1][j - weight[i]]就是不放入物品i时候的背包最大价值。
当加上物品i的价值value[i]，则等于放入物品i的最大价值。

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
dp数组的初始化。

当背包容量为0时，装入不了任务物品，所以，当j=0时，$dp[i][0] = 0;
当i = 物品0时，需要判断当前j背包容量是否小于weight[i]，小于的话也初始化为0，因为背包装不下物品0，所以最大价值为0；
大于等于的话初始化物品0的价值即可。dp[0][j] = value[0];
对应下图的话，就是假设物品0的重量为2的话，则j=1的位置应该=0。
当i != 0 && j != 0 的情况，也初始化为0即可，因为递推公式有求max的过程。

遍历顺序：先遍历物品还是先遍历背包重量都可以。

code

<?php
//dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
function oneBag(){
   $weight = [1, 3, 4];
   $value = [15, 20, 30];
   $bagweight = 4;
   $dp = [];
   $wLen = count($weight);
   $vLen = count($value);

   for($i = 0; $i < $wLen; $i++){
       for($j = 0; $j <= $bagweight; $j++){
            $dp[$i][$j] = 0;
       }
   }
   //初始化每种背包容量的最低价值为最小价值
   for ($j = $weight[0]; $j <= $bagweight; $j++) {
         $dp[0][$j] = $value[0];
   }
   //因为物品0的情况已经在上面初始化完成了，所以这里i从1开始遍历
   for($i = 1; $i < $wLen; $i++){
        for ($j = 1; $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]);
             }
        }
    }

    return $dp[$wLen-1][$bagweight];
}
print_r(oneBag());
?>

背包理论基础 01背包一维解法

解题方法

实际解法与之前不同路径的节省空间解法一样使用的滚动数组。一个长度为 n 数组（x 轴方向），不断的更新 m 次 (y 轴方向)。

确定dp数组的定义：dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
一维dp数组的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 同样的一维解法也有两个状态：放物品i与不放入物品i。

放入物品i

dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j weight[i]的背包所背的最大价值。其中j - weight[i]与二维一样是背包没放入物品i的容量状态，也就是i-1的状态。
dp[j - weight[i]] + value[i] 表示容量为 j - 物品i重量的背包加上物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）

不放入物品i

滚动数组的本质是：在上一个状态的数组基础上修改，所以dp[j] = dp[j]。可以理解为复制了一份同样的数组。不放入物品i则当前数值不用修改，等于上一个状态。

dp数组初始化：dp[j] = 0。因为容量为0的背包，所背的物品价值就是0；大于0时因为有求max操作，所以dp数组整体初始化为0即可。
遍历顺序：先遍历物品，再倒序遍历背包。因为不倒序遍历的话，会存在重复利用物品的问题。

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15。如果正序遍历

dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

code

<?php
//dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
function oneBag(){
   $weight = [1, 3, 4];
   $value = [15, 20, 30];
   $bagweight = 4;
   $dp = [];
   $wLen = count($weight);
   $vLen = count($value);

    for($j = 0; $j <= $bagweight; $j++){
        $dp[$j] = 0; 
    }

    for($i = 0; $i < $wLen; $i++){
        for ($j = $bagweight; $j >= $weight[$i]; $j--) {
             $dp[$j] = max($dp[$j], $dp[$j - $weight[$i]] + $value[$i]);
        }
    }

    return $dp[$bagweight];
}
print_r(oneBag());
?>

416. 分割等和子集

解题方法

难点在于如何抽象为背包问题。

背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。

确定dp数组以及下标的含义
01背包中，dp[j] 表示：容量为j的背包，所背的物品价值最大可以为dp[j]。
确定递推公式
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
这里由于num可以抽象为重量与价值相等的物品，所以转换为dp[j] = max(dp[j], dp[j - num[i]] + nums[i]);
dp数组初始化：初始化为0即可。
遍历顺序：与上面一维解题一致。
需要注意的是，题目给出的是是否可以分割成两个子集，使得两个子集的元素和相等。即背包容量为nums/2。如果数组和不为偶数则出现小数0.5，数组内元素如何相加都不能出现0.5的情况。所以直接return false即可。假设nums = [1,1,3,4] 背包容量为4.5，而数组内没有元素组合可以=4.5，所以return false。
举例推到dp数值
如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

code

<?php
class Solution {

    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function canPartition($nums) {
        $sum = array_sum($nums);
        //数组和不为偶数
        if($sum % 2 == 1) return false;
        //背包容量
        $bagweight = array_sum($nums)/2;

        $dp = [];
        //初始化
        for($j = 0; $j <= $bagweight; $j++){
            $dp[$j] = 0;
        }

        for($i = 0; $i < count($nums); $i++){
            for($j = $bagweight; $j >= $nums[$i]; $j--){
                //$nums 既是价值数组也是重量数组
                $dp[$j] = max($dp[$j], $dp[$j-$nums[$i]] + $nums[$i]);
            }
        }
        //如果背包容量与最大价值相等，则return true
        if($dp[$bagweight] == $bagweight) return true;
        return false;
    }
}