0/1背包问题总结

avatar
作者
猴君
阅读量:4

文章目录


在这里插入图片描述
博客主页:lyyyyrics

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

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

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

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

数学公式可以表示为:

Maximize ∑ i = 1 n v i x i subject to ∑ i = 1 n w i x i ≤ W x i ∈ { 0 , 1 } , i = 1 , 2 , . . . , n \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*} Maximizesubject toi=1nvixii=1nwixiWxi{0,1},i=1,2,...,n

其中, x i x_i xi表示第 i i i个物品是否放入背包中。若 x i = 1 x_i=1 xi=1,表示放入;若 x i = 0 x_i=0 xi=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++代码示例展示了具体的实现步骤。

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

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

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!