0


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


🎈 作者:Linux猿

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

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

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


背包问题在算法中经常用到,尤其是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 背包算法解决。


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



本文转载自: https://blog.csdn.net/u011074149/article/details/123099348
版权归原作者 Linux猿 所有, 如有侵权,请联系我们删除。

“【数据结构和算法】01 背包的应用”的评论:

还没有评论