【数据结构和算法】01 背包的应用

举报
Linux猿 发表于 2022/02/27 22:49:06 2022/02/27
【摘要】 🎈 作者:Linux猿🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!🎈 关注专栏: 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬目录🍓一、题目描述🍓二、测试样例🥝2.1 样例 1🥝2.2 样例 2🍓三、算法思路🍓四、代码实...


🎈 作者:Linux猿

🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

🎈 关注专栏: 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬


目录

🍓一、题目描述

🍓二、测试样例

🥝2.1 样例 1

🥝2.2 样例 2

🍓三、算法思路

🍓四、代码实现

🍓五、复杂度分析

🥝5.1 时间复杂度

🥝5.2 空间复杂度

🍓六、总结


背包问题在算法中经常用到,尤其是01 背包,下面就来看一下 01 背包的应用。

🍓一、题目描述

给定一个只包含正整数的非空数组 nums 。请判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

提示:

1 <= nums.length <= 200

1 <= nums[i] <= 100


🔶🔶🔶🔶🔶 我是华丽的分割线 🔶🔶🔶🔶🔶


🍓二、测试样例

🥝2.1 样例 1

输入:nums = [1,5,11,5]

输出:true

说明:数组可以分割成 [1, 5, 5] 和 [11] ,两者之和都为 11。

🥝2.2 样例 2

输入:nums = [1,2,3,5]

输出:false

说明:数组之和为 11,显然不能分割成两个元素和相等的子集。


🔶🔶🔶🔶🔶 我是华丽的分割线 🔶🔶🔶🔶🔶


🍓三、算法思路

本题可以将题意简化为:

判断正整数数组 nums 是否存在一个子集,这个子集的和为 nums 数组中所有值和的一半。

题意转化后就好解题了,就是在 nums 中挑选一些数字,这些数字之和正好组成一个给定的数,很明显是一个背包问题,因为物品(nums 中的数字)不能重复选择,所以是一个 背包问题

01 背包问题可以 关注专栏 数据结构和算法成神路【精讲】

注意:这里要求背包正好装满(挑选的子集中的数字之和正好为 nums 数组所有数和的一半)。


🔶🔶🔶🔶🔶 我是华丽的分割线 🔶🔶🔶🔶🔶


🍓四、代码实现

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        //1. 计算 nums 中所有数字的和
        for(int i = 0; i < (int)nums.size(); ++i) {
            sum += nums[i];
        }
        // sum 如果为奇数,必定不能分割
        if(sum%2) return false;
        sum /= 2;

        //使用 bool 类型即可
        bool dp[sum + 5];
        memset(dp, false, sizeof(dp));
        dp[0] = true;
        // 01 背包
        for(int i = 0; i < (int)nums.size(); ++i) {
            for(int j = sum; j >= nums[i]; --j) {
                if(dp[j - nums[i]]) {
                    dp[j] = true;
                }
            }
        }
        return dp[sum];
    }
};

int main()
{
    //test
    int a[] = {1, 5, 11, 5};
    vector<int>nums(a, a + 4);

    //int b[] = {2, 2, 3, 5};
    //vector<int>nums(b, b + 4);

    Solution obj;
    cout<<obj.canPartition(nums)<<endl;
    return 0;
}

其中,sum 为计算 nums 数组中的所有数字之和。第一个 for 循环计算 nums 数组中的所有数字之和。

接下来的两层 for 循环是 01 背包算法,遍历数组判断容量为 sum/2 的背包是否能够正好装满。

通过后的截图如下所示。 

​ 图1 通过截图



🔶🔶🔶🔶🔶 我是华丽的分割线 🔶🔶🔶🔶🔶


🍓五、复杂度分析

🥝5.1 时间复杂度

时间复杂度为:O(n*m),其中,n 为 nums 数组长度,m 为 nums 数组值总和的一半。在上述代码中,时间复杂度主要在01 背包(两层 for 循环)处,所以总的时间复杂度为 O(n * m)。

🥝5.2 空间复杂度

空间复杂度:O(m),在上述算法中,使用到了一个 dp 数组记录背包的容量,所以空间复杂度为 O(m)。


🔶🔶🔶🔶🔶 我是华丽的分割线 🔶🔶🔶🔶🔶


🍓六、总结

本题需要在理解题意的基础上,转化为 01 背包算法解决。


🎈 感觉有帮助记得「一键三连支持下哦!有问题可在评论区留言💬,感谢大家的一路支持!🤞猿哥将持续输出「优质文章回馈大家!🤞🌹🌹🌹🌹🌹🌹🤞



🎈 作者:Linux猿

🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

🎈 关注专栏: 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200