关于算法:经典动态规划子集背包问题

读完本文,你能够去力扣拿下如下题目:

416.宰割等和子集

———–

上篇文章 经典动静布局:0-1 背包问题 详解了通用的 0-1 背包问题,明天来看看背包问题的思维可能如何使用到其余算法题目。

而且,不是常常有读者问,怎么将二维动静布局压缩成一维动静布局吗?这就是状态压缩,很容易的,本文也会提及这种技巧。

一、问题剖析

先看一下题目:

算法的函数签名如下:

// 输出一个汇合,返回是否可能宰割成和相等的两个子集
bool canPartition(vector<int>& nums);

对于这个问题,看起来和背包没有任何关系,为什么说它是背包问题呢?

首先回顾一下背包问题大抵的形容是什么:

给你一个可装载重量为 W 的背包和 N 个物品,每个物品有分量和价值两个属性。其中第 i 个物品的分量为 wt[i],价值为 val[i],当初让你用这个背包装物品,最多能装的价值是多少?

那么对于这个问题,咱们能够先对汇合求和,得出 sum,把问题转化为背包问题:

给一个可装载重量为 sum / 2 的背包和 N 个物品,每个物品的分量为 nums[i]。当初让你装物品,是否存在一种装法,可能恰好将背包装满

你看,这就是背包问题的模型,甚至比咱们之前的经典背包问题还要简略一些,上面咱们就间接转换成背包问题,开始套前文讲过的背包问题框架即可。

PS:我认真写了 100 多篇原创,手把手刷 200 道力扣题目,全副公布在 labuladong的算法小抄,继续更新。倡议珍藏,依照我的文章程序刷题,把握各种算法套路后投再入题海就蛟龙得水了。

二、解法剖析

第一步要明确两点,「状态」和「抉择」

这个前文 经典动静布局:背包问题 曾经具体解释过了,状态就是「背包的容量」和「可抉择的物品」,抉择就是「装进背包」或者「不装进背包」。

第二步要明确 dp 数组的定义

依照背包问题的套路,能够给出如下定义:

dp[i][j] = x 示意,对于前 i 个物品,以后背包的容量为 j 时,若 xtrue,则阐明能够恰好将背包装满,若 xfalse,则阐明不能恰好将背包装满。

比如说,如果 dp[4][9] = true,其含意为:对于容量为 9 的背包,若只是用前 4 个物品,能够有一种办法把背包恰好装满。

或者说对于本题,含意是对于给定的汇合中,若只对前 4 个数字进行抉择,存在一个子集的和能够恰好凑出 9。

依据这个定义,咱们想求的最终答案就是 dp[N][sum/2],base case 就是 dp[..][0] = truedp[0][..] = false,因为背包没有空间的时候,就相当于装满了,而当没有物品可抉择的时候,必定没方法装满背包。

第三步,依据「抉择」,思考状态转移的逻辑

回忆方才的 dp 数组含意,能够依据「抉择」对 dp[i][j] 失去以下状态转移:

如果不把 nums[i] 算入子集,或者说你不把这第 i 个物品装入背包,那么是否可能恰好装满背包,取决于上一个状态 dp[i-1][j],继承之前的后果。

如果把 nums[i] 算入子集,或者说你把这第 i 个物品装入了背包,那么是否可能恰好装满背包,取决于状态 dp[i-1][j-nums[i-1]]

首先,因为 i 是从 1 开始的,而数组索引是从 0 开始的,所以第 i 个物品的分量应该是 nums[i-1],这一点不要搞混。

dp[i - 1][j-nums[i-1]] 也很好了解:你如果装了第 i 个物品,就要看背包的残余分量 j - nums[i-1] 限度下是否可能被恰好装满。

换句话说,如果 j - nums[i-1] 的分量能够被恰好装满,那么只有把第 i 个物品装进去,也可恰好装满 j 的分量;否则的话,分量 j 必定是装不满的。

最初一步,把伪码翻译成代码,解决一些边界状况

以下是我的 C++ 代码,齐全翻译了之前的思路,并解决了一些边界状况:

bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    // 和为奇数时,不可能划分成两个和相等的汇合
    if (sum % 2 != 0) return false;
    int n = nums.size();
    sum = sum / 2;
    vector<vector<bool>> 
        dp(n + 1, vector<bool>(sum + 1, false));
    // base case
    for (int i = 0; i <= n; i++)
        dp[i][0] = true;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (j - nums[i - 1] < 0) {
               // 背包容量有余,不能装入第 i 个物品
                dp[i][j] = dp[i - 1][j]; 
            } else {
                // 装入或不装入背包
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j-nums[i-1]];
            }
        }
    }
    return dp[n][sum];
}

PS:我认真写了 100 多篇原创,手把手刷 200 道力扣题目,全副公布在 labuladong的算法小抄,继续更新。倡议珍藏,依照我的文章程序刷题,把握各种算法套路后投再入题海就蛟龙得水了。

三、进行状态压缩

再进一步,是否能够优化这个代码呢?留神到 dp[i][j] 都是通过上一行 dp[i-1][..] 转移过去的,之前的数据都不会再应用了。

所以,咱们能够进行状态压缩,将二维 dp 数组压缩为一维,节约空间复杂度:

bool canPartition(vector<int>& nums) {
    int sum = 0, n = nums.size();
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;
    sum = sum / 2;
    vector<bool> dp(sum + 1, false);
    // base case
    dp[0] = true;

    for (int i = 0; i < n; i++) 
        for (int j = sum; j >= 0; j--) 
            if (j - nums[i] >= 0) 
                dp[j] = dp[j] || dp[j - nums[i]];

    return dp[sum];
}

这就是状态压缩,其实这段代码和之前的解法思路完全相同,只在一行 dp 数组上操作,i 每进行一轮迭代,dp[j] 其实就相当于 dp[i-1][j],所以只须要一维数组就够用了。

惟一须要留神的是 j 应该从后往前反向遍历,因为每个物品(或者说数字)只能用一次,免得之前的后果影响其余的后果

至此,子集切割的问题就齐全解决了,工夫复杂度 O(n\*sum),空间复杂度 O(sum)。

_____________

我的 在线电子书 有 100 篇原创文章,手把手带刷 200 道力扣题目,倡议珍藏!对应的 GitHub 算法仓库 曾经取得了 70k star,欢送标星!

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据