您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

详解背包问题--以及对它进行状态压缩--分割等和子集

文章目录

  • 题目
  • 背包详解
      • 代码

题目

在这里插入图片描述
image.png

背包详解

如何判断是背包问题呢?只要一个问题可以看作为将物体装入背包的过程,那么它就是背包问题。
比如本题,只要求出sum/2之后,接下来要求出数组中的元素是否有和正好为该数的,
而这个过程sum/2就相当于背包的容量,而数组中的元素就是装入其中的物体,确定为背包问题后,
我们还需要清楚是哪一类背包问题–到底是物体使用次数受限还是不受限。
此题物体使用次数只有一次,所以是01背包问题,接下来就是定义dp和推导dp关系的过程了。

  1. 定义dp[i][j]为判断前i个元素能否正好填满j容量。
  2. 则base case为dp[..][0]=true.
  3. 关于背包问题dp关系都是放与不放的过程与dp[i][j]的联系。
  4. 当放入第i个元素能否填满就看dp[i-1][j-nums[i]],而不放入第i个元素能否填满就看dp[i-1][j].
  5. 只要第四点中有一个为true则dp[i][j]就为true。
  6. 故dp关系为dp[i][j] = dp[i-1][j]||dp[i-1][j-nums[i]]
  7. 最后由于当前的dp关系只依赖上一行的结果,所以可以通过状态压缩变为:
    dp[j] = dp[j]||dp[j-nums[i]],由于需要每次保证为上一行的结果,所以一维数组的遍历方向需要调整为从后往前遍历。

代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int t:nums){
            sum += t;
        //如果sum为奇数,则不可能分割成两个和相等的情况
        }if(sum%2 != 0)
            return false;
        sum /= 2;
        //0 1背包问题,因为每个元素只能选择一次
        bool dp[sum+1];
        memset(dp,false,sizeof(dp));
        dp[0] = true;
        //装与不装的关系,只是这是一个状态压缩的一维dp
        for(int num:nums){
            for(int i=sum;i>=num;i--){
                dp[i] = dp[i] || dp[i-num];
            }
        }
        return dp[sum];
    }
};

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进