0/1背包问题总结

文章目录

🍇什么是0/1背包问题？
🍈例题
- 🍉1.分割等和子集
- 🍉2.目标和
- 🍉3.最后一块石头的重量Ⅱ
🍊总结

博客主页：lyyyyrics

🍇什么是0/1背包问题？

0/1背包问题是一个经典的组合优化问题，其描述如下：

假设有一个背包，它能够承载一定的重量。现在有一组物品，每个物品有各自的重量和价值。我们的目标是在不超过背包承载重量的前提下，选择一些物品放入背包中，使得背包中物品的总价值最大化。

具体来说，假设有 $n$ 个物品，其重量分别为 $w_1, w_2, ..., w_n$ ，对应的价值分别为 $v_1, v_2, ..., v_n$ 。背包的承载重量为 $W$ 。我们需要在这 $n$ 个物品中选择一些放入背包中，使得这些物品的总重量不超过 $W$ ，且总价值最大化。

数学公式可以表示为：

$\begin{align*} \text{Maximize} \quad & \sum_{i=1}^{n} v_ix_i \\ \text{subject to} \quad & \sum_{i=1}^{n} w_ix_i \leq W \\ & x_i \in \{0, 1\}, \quad i=1,2,...,n \end{align*}$

其中， $x_i$ 表示第 $i$ 个物品是否放入背包中。若 $x_i=1$ ，表示放入；若 $x_i=0$ ，表示不放入。

🍈例题

🍉1.分割等和子集

题目：

样例输出和输入：

根据描述，这道题就是让我们求一个数组是否能将其分成两块，然后这两块是相等的，如果能返回true，如果不能则返回false。
算法原理：
首先我们注意到，这道题要将数组分成两个部分，这两个部分是否相等，我们可以转化为分成一个部分，这个部分是数组总和的一半？很显然是可以的，这样转换之后其实就已经是背包问题了，这个数组中的数就是物品，数组中的数就代表每个物品的价值，然后数组中的数的总和的一半就是这个背包的容量，问题就转化为，我们是否可以从数组中挑出一些物品，使得物品的体积恰好能把这个背包塞满？
状态表示：dp[i][j]表示前i个数中的所有的选法中，是否存在和为j的选法，如果存在则是true，如果不存在则就是false。
状态转移方程：状态转移方程还是考虑i位置和j位置。
在这里插入图片描述
如果能选的话，应该是选和不选中有一个满足就够了，所以这里应该还要取一个||,dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]]
初始化：
首先看第一行，从1开始，从0个数中选，和为1的，这种情况是不存在的，所以应该是false，后面的从0个数中选的都是false，，我们来看第一列，从0个数中选和为0，那就是不选，所以为true，从1个数中选和为0，可以不选，也是true，所以我们只需要初始化第一列，初始化为true。
代码：

class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int n = nums.size();
        int sum = 0;
        //求和
        for (auto e : nums)sum += e;
        //如果和是奇数的话直接返回
        if (sum % 2 == 1)return false;
        //先定义一个aim表示和的一半
        int  aim = sum / 2;
        //创建dp表
        vector<vector<bool>> dp(n + 1, vector<bool>(aim + 1));
        //初始化dp表的第一列为true，因为如果和为零的话是有可能的。
        //如果什么都不选的话，当前和就是0
        for (int i = 0;i <= n;i++)
        {
            dp[i][0] = true;
        }
        for (int i = 1;i <= n;i++)
        {
            for (int j = 1;j <= aim;j++)
            {
                //不选的话就是前一个状态的bool值
                dp[i][j] = dp[i - 1][j];
                //如果能选的话，只要有一种满足就表示满足
                if (j >= nums[i - 1])dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
        //返回和为aim的状态
        return dp[n][aim];
    }
};

运行结果：
在这里插入图片描述

🍉2.目标和

题目：

样例输出和输入：

这道题是给定一个数组，我们可以将数组中数的符号我们可以随便改，最后串成一个加减法的式子，然后这个式子的值为target即可，这道题当然不是让我们返回true或者false，而是让我们返回方法的总数。
算法原理：
这道题其实我们可以将当中的数划分为两类：
在这里插入图片描述
我们将b规定为负数的绝对值。
所以最后可以得出：
所以我们只需要看这个数组中是否组合能使得这个组合最后的和是a即可。
状态表示：dp[i][j]表示从前i个数中选，所有选法中和为j的方法。
状态转移方程：状态转移方程还是看第i个位置：
在这里插入图片描述
如果能选的话，则方法总数就是选和不选的和：dp[i][j]+=dp[i-1][j-nums[i]]，但是有一个条件：j>nums[i]。

代码：

class Solution 
{
public:
    int findTargetSumWays(vector<int>& nums, int target)
    {
        int n = nums.size();
        int sum = 0;
        for (auto e : nums)sum += e;
        int aim = (sum + target) / 2;
        if (aim < 0 || (sum + target) % 2 == 1)return 0;
        vector<vector<int>> dp(n + 1, vector<int>(aim + 1));
        dp[0][0] = 1;
        for (int i = 1;i <= n;i++)
        {
            for (int j = 0;j <= aim;j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1])dp[i][j] += dp[i - 1][j - nums[i - 1]];
            }
        }
        return dp[n][aim];
    }
};

运行结果：
在这里插入图片描述

🍉3.最后一块石头的重量Ⅱ

题目：

这道题的题目是“最后一块石头的重量 II”。

样例输出和输入：

给定一堆石头的重量数组stones，在每一回合中，选出两块石头粉碎，最后剩下的石头的重量可能为：

如果选出的两块石头重量相等，那么两块石头都会被完全粉碎；
如果选出的两块石头重量不相等，重量为较小的石头将会完全粉碎，而重量为较大的石头新重量为较大石头的重量减去较小石头的重量。

问题要求找到最后剩下的石头的最小可能重量。如果没有剩下的石头，返回0。给定一堆石头的重量数组stones，在每一回合中，选出两块石头粉碎，最后剩下的石头的重量可能为：

如果选出的两块石头重量相等，那么两块石头都会被完全粉碎；
如果选出的两块石头重量不相等，重量为较小的石头将会完全粉碎，而重量为较大的石头新重量为较大石头的重量减去较小石头的重量。

问题要求找到最后剩下的石头的最小可能重量。如果没有剩下的石头，返回0。

算法原理：

首先我们模拟一遍这个过程：
在这里插入图片描述

注意：上述过程是建立在前一个比后一个大的基础上模拟的
我们可以发现：当中的数也是有正有负，相当与也可以分成两个分类，一个正一个负：
在这里插入图片描述

其实我们不难看出，当a和b最接近的时候，这时候差值最小，所以这道题我们就可以转换成了0/1背包问题：
相当于a和b都接近于sum/2，所以这道题的背包容量是sum/2，
状态表示：dp[i][j]表示前i个物品中选，总和不超过j的，最大的和。
状态转移方程：在这里插入图片描述
当存在第一种情况的是否需要和不选的情况求一个最大值：dp[i][j]=max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]
代码：

int lastStoneWeightII(vector<int>& stones)
{
	int n = stones.size();
	int sum = 0;
	for (auto e : stones)sum += e;
	vector<vector<int>> dp(n + 1, vector<int>(sum / 2 + 1));
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= sum / 2;j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= stones[i - 1])dp[i][j] = max(dp[i - 1][j - stones[i - 1]] + stones[i - 1], dp[i - 1][j]);
		}
	}
	int a = dp[n][sum / 2];
	int b = sum - a;
	return abs(a - b);
}

空间优化过的代码：二维---->一维

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones)
    {
        int n = stones.size();
        int sum = 0;
        for (auto e : stones)sum += e;
        vector<int> dp(sum / 2 + 1);
        for (int i = 1;i <= n;i++)
            for (int j = sum / 2;j >= stones[i - 1];j--)
                dp[j] = max(dp[j - stones[i - 1]] + stones[i - 1], dp[j]);
        int a = dp[sum / 2];
        int b = sum - a;
        return abs(a - b);
    }
};