01背包之---应用篇

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

上文我们讲完了01背包的一维的写法，了解了01背包问题的模型，就是每个物品可以被拿一次，求在有限的背包容量下，所能取得的最大价值是多少，但在刷题过程中题目往往不是直接给你一个这样的模板然后让你去求，所以我们今天来讲三种明面上不是背包问题的题目但其实就是01背包的题目
下面例题解答我们统一用一维dp解答，不仅代码比二维简洁，而且复杂度更低

一、01背包之—背包是否能被装满？

例题1.

分析题意

首先这道题要我们把一个数组分成两个数组，两个数组的和相同
首先这两个数组的各自总和ans肯定为总数组的和sum/2；
那么如果这个原数组的和sum为奇数，肯定就不能分成功，这个我们现在可以单独判出来

其次我们仔细想一下，我们现在已知什么？ 我们知道原数组总和sum
那是不是也知道了要分成两个数组，每个数组的和为 sum/2
是不是问题就转换为求背包容量为sum/2的一个背包，从原数组中选商品，看能不能正好装满这个背包
我们直接求背包容量为sum/2所能装的最大价值即可，如果装的最大价值就等于sum/2，那意思是不是就是可以装满这个背包，从而可以成功分为两个数组呢？

那么接下来我们直接上代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int i=0;i<nums.size();i++)sum+=nums[i];//求数组总和
        int dp[10001];
        //初始化
        for(int i=0;i<10001;i++)dp[i]=0;
        if(sum%2==1)return false;
        int target=sum/2;
        for(int i=0;i<nums.size();i++)//遍历物品
        {
            for(int j=target;j>=nums[i];j--)
            {
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[target]==target)return true;
        return false;
    }
};

关于dp数组的初始化以及遍历问题，请回顾上篇文章，这里不再过多讲解

例题2.

分析题意

这道题其实更第一题很类似
大家可以发现，其实也是分成两个数组，然后使两个数组的差最小，大家仔细想想，是不是这个道理？
我们直接上代码

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(int i=0;i<stones.size();i++)sum+=stones[i];//计算总和
        int dp[10001];
        for(int i=0;i<10001;i++)dp[i]=0;//初始化
        int target=sum/2;
        for(int i=0;i<stones.size();i++)
        {
            for(int j=target;j>=stones[i];j--)
            {
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        if(2*dp[target]==sum)return 0;
        return sum-2*dp[target];
    }
};

二、01背包之—装满背包有多少种组合?

例题1.

分析题意

刚看到题目的时候我也一脸懵逼，后来发现，这就是排列组合的题目，我们可以把原数组分成两块，一方存储加号的元素，一方存储减号的元素，我们只需要找到有多少种组合的和满足与其中一方的和就行了，我们这里以加号的元素为准

假设所有+号的元素的总和为x 所有-号的元素的总和为y 原数组总和为sum 目标值为target
那么 x+y=sum
x-y=target
所以 x=(target+sum)/2
所以我们只需要找到装满容量为x的背包 有多少种组合即可
但这里有个注意点，这个 (target+sum)/2一定可以被整除嘛？？
答案是一定的，不然凑不出结果，大家可以在草稿纸上写一下

所以我们现在有了dp数组
dp[j]表示容量为j的背包 装满后有多少种组合

那么递推公式呢？
dp[j]+=dp[j-nums[i]]
为什么呢？
大家可以想一下
dp[5]一定由dp[1]+dp[2]+dp[3]+dp[4]相加而来，那么为什么呢
比如我此时dp[1]=1,表示装满容量为1的背包有1种方式，那么此时我如果再装一个4的物品，是不是直接满容量了，所以dp[5]可以从dp[1]得来，同理可得dp[5]=dp[1]+dp[2]+dp[3]+dp[4]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int i=0;i<nums.size();i++)sum+=nums[i];//计算总和
        int jiafa=(target+sum)/2;
        if(abs(target)>sum||(target+sum)%2==1)return 0;//无法构造出
       //装满容量为i的背包有dp[i]种组合
        int dp[10001];
        for(int i=1;i<10001;i++)dp[i]=0;
        dp[0]=1;
        for(int i=0;i<nums.size();i++)
        {
            for(int j=jiafa;j>=nums[i];j--)
            {
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[jiafa];
    }
};

三、01背包之—容量为N的背包最多可以装多少物品?

例题1.

分析题意

我们仔细分析题目，我们可以把m个0 n个1当成背包容量，大家想一想是不是这样
我们最初一开始讲的01背包问题的时候，只有一个背包容量，然后求在这个容量的情况下，所能装的最大物品价值为多少，当时我们写的是一维的dp[j] 只有一个容量j 那这里我们是不是相当于有两个容量 m和n，dp[m][n]表示在有m个0和n个1的情况下 所能装的最多的字符串个数为dp[m][n]个

此时我们注意！！！，我们这虽然开的是二维的dp[m][n]，但这两个变量都代表背包容量，相当于01背包中的dp[j]，如果讲01背包问题写成二维的dp[i][j]，那么我们这里就要写成dp[i][m][n]三维表示，因为i表示的是物品，后面两个都是背包容量，大家不要搞混

一维的递推公式维dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
其实我们通过对比很快就能发现此题的递推公式为 dp[m][n]=max(dp[m][n],dp[m-weight[i]][n-weight[i]]+1) 这两个的意思都是要么不拿此物品 要么拿

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int dp[m+5][n+5];//容量为m和n的背包能装多少个物品
        for(int i=0;i<m+2;i++)
        {
            for(int j=0;j<n+2;j++)
            {
                dp[i][j]=0;
            }
        }
        dp[0][0]=0;
        //求dp[m][n];//m个0 n个1
        for(int i=0;i<strs.size();i++)//遍历物品
        {
            int x=0;//记录有多少个0
            int y=0;//记录有多少个y
            for(int k=0;k<strs[i].size();k++)
            {
                if(strs[i][k]=='0')x++;
                else
                {
                    y++;
                }
            }
            //遍历背包
            for(int j1=m;j1>=x;j1--)
            {
                for(int j2=n;j2>=y;j2--)
                {
                    dp[j1][j2]=max(dp[j1][j2],dp[j1-x][j2-y]+1);
                }
            }
        }
        return dp[m][n];

    }
};

总结

今天讨论了01背包问题的背包是否能被装满，装满背包有多少种组合的问题，容量为N的背包最多可以装多少物品我们都是用一维来写，这样复杂度更低，判断背包是否能被装满，直接判断背包最大容量时可以装多少价值即可，如果和背包容量相等，就是装满了，在讨论装满背包有多少种组合的问题的时候，我们用递推公式 dp[j]+=dp[j-nums[i]] 即可
当判断一定容量的背包能装多少个的时候，在dp递推的时候里面把加value[i]改成+1即可，因为要求的不是最大价值，而是最多的数量