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{array}{rl}\text{Maximize}& \sum _{i=1}^n{v}_i{x}_i\\ \text{subject to}& \sum _{i=1}^n{w}_i{x}_i\le W\\ & x_i\in \{0,1\},i=1,2,...,n\end{array}$$

其中，$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，在每一回合中，选出两块石头粉碎，最后剩下的石头的重量可能为：

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

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

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

问题要求找到最后剩下的石头的最小可能重量。如果没有剩下的石头，返回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);     } }; 

运行结果：

🍊总结

0/1 背包问题是组合优化中的经典问题，通过研究和解决这一问题，可以深入理解动态规划的基本思想和应用。本文详细介绍了0/1背包问题的定义、数学模型及其动态规划解法，并通过C++代码示例展示了具体的实现步骤。

通过本次总结，希望读者能够掌握如何将理论知识应用于实际问题，理解状态转移方程的推导过程，以及如何优化算法以提升效率。背包问题不仅在学术研究中具有重要意义，还广泛应用于资源分配、项目管理等实际领域。掌握这一问题的解决方法，可以为解决更复杂的优化问题打下坚实的基础。

在今后的学习中，建议读者多多练习不同变种的背包问题，如完全背包、多重背包问题等，以进一步提升自己的算法设计和分析能力。感谢阅读，希望本文对你的学习和应用有所帮助。