网站开发语言排行,招聘网站开发价格,专业开发网站建设哪家好,网站建站网站80s隐秘而伟大01背包问题的空间优化与边界处题目解析
01背包问题是经典的动态规划问题#xff0c;旨在选择若干物品装入背包#xff0c;使得总价值最大且不超过背包容量。每个物品只能选或不选#xff08;0或1#xff09;#xff0c;不可分割。
选和不选是01背包问题最大的特征
例题…01背包问题的空间优化与边界处题目解析
01背包问题是经典的动态规划问题旨在选择若干物品装入背包使得总价值最大且不超过背包容量。每个物品只能选或不选0或1不可分割。
选和不选是01背包问题最大的特征
例题
01背包
题目链接
01背包
要点
老师代码
#include iostream
#include string.husing namespace std;
const int N 1010;
int n, V, v[N], w[N];
int dp[N][N];int main()
{// 读⼊数据cin n V;for(int i 1; i n; i)cin v[i] w[i];// 解决第⼀问for(int i 1; i n; i)for(int j 0; j V; j) // 修改遍历顺序{dp[i][j] dp[i - 1][j];if(j v[i])dp[i][j] max(dp[i][j], dp[i - 1][j - v[i]] w[i]);}cout dp[n][V] endl;// 解决第⼆问memset(dp, 0, sizeof dp);for(int j 1; j V; j) dp[0][j] -1;for(int i 1; i n; i)for(int j 0; j V; j) // 修改遍历顺序{dp[i][j] dp[i - 1][j];if(j v[i] dp[i - 1][j - v[i]] ! -1)dp[i][j] max(dp[i][j], dp[i - 1][j - v[i]] w[i]);}cout (dp[n][V] -1 ? 0 : dp[n][V]) endl;return 0;
}空间优化
#include iostream
#include string.h
using namespace std;const int N 1010;
int n, V, v[N], w[N];
int dp[N];int main()
{// 读⼊数据cin n V;for(int i 1; i n; i)cin v[i] w[i];// 解决第⼀问for(int i 1; i n; i)for(int j V; j v[i]; j--) // 修改遍历顺序dp[j] max(dp[j], dp[j - v[i]] w[i]);cout dp[V] endl;// 解决第⼆问memset(dp, 0, sizeof dp);for(int j 1; j V; j) dp[j] -1;for(int i 1; i n; i)for(int j V; j v[i]; j--)if(dp[j - v[i]] ! -1)dp[j] max(dp[j], dp[j - v[i]] w[i]);cout (dp[V] -1 ? 0 : dp[V]) endl;return 0;
}老师思路
第一问 状态表⽰dp[i][j] 表⽰从前 i 个物品中挑选总体积「不超过」 j 所有的选法中能挑选出来的最⼤价值 状态转移⽅程线性 dp 状态转移⽅程分析⽅式⼀般都是根据「最后⼀步」的状况来分情况讨论 i. 不选第 i 个物品相当于就是去前 i - 1 个物品中挑选并且总体积不超过 j 。此时 dp[i][j] dp[i - 1][j] ii. 选择第 i 个物品那么我就只能去前 i - 1 个物品中挑选总体积不超过 j - v[i] 的物品。此时 dp[i][j] dp[i - 1][j - v[i]] w[i] 。但是这种状态不⼀定存在因此需要特判⼀下。综上状态转移⽅程为 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i]) 。 初始化我们多加⼀⾏⽅便我们的初始化此时仅需将第⼀⾏初始化为 0 即可。因为什么也不选也能满⾜体积不⼩于 j 的情况此时的价值为 0 。 填表顺序根据「状态转移⽅程」我们仅需「从上往下」填表即可。 返回值根据「状态表⽰」返回 dp[n][V] 。
第二问
第⼆问仅需微调⼀下 dp 过程的五步即可。 因为有可能凑不⻬ j 体积的物品因此我们把不合法的状态设置为 -1 。 状态表⽰dp[i][j] 表⽰从前 i 个物品中挑选总体积「正好」等于 j 所有的选法中能挑选出来的最⼤价值。 状态转移⽅程dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i]) 。但是在使⽤ dp[i - 1][j - v[i]] 的时候不仅要判断 j v[i] ⼜要判断 dp[i- 1][j - v[i]] 表⽰的情况是否存在也就是 dp[i - 1][j - v[i]] ! -1 初始化我们多加⼀⾏⽅便我们的初始化i. 第⼀个格⼦为 0 因为正好能凑⻬体积为 0 的背包 ii. 但是第⼀⾏后⾯的格⼦都是 -1 因为没有物品⽆法满⾜体积⼤于 0 的情况 填表顺序根据「状态转移⽅程」我们仅需「从上往下」填表即可。 返回值由于最后可能凑不成体积为 V 的情况因此返回之前需要「特判」⼀下。
我的代码
#include iostream
#include vector
using namespace std;int main()
{int n, v;cin n v;vectorint sz(n 1);vectorint val(n 1);for(int i 1; i n; i) cin sz[i] val[i];//状态表示vectorvectorint dp1(n 1, vectorint(v 1));auto dp2 dp1;//初始化for(int j 1; j v; j) dp2[0][j] -1;//使空位置的物品价值等于j是不存在的而不是物品价值为0所以填入-1//填表for(int i 1; i n; i){for(int j 0; j v; j){dp1[i][j] dp1[i - 1][j];if(sz[i] j) dp1[i][j] max(dp1[i][j], dp1[i - 1][j - sz[i]] val[i]);dp2[i][j] dp2[i - 1][j];if(sz[i] j dp2[i - 1][j - sz[i]] ! -1) dp2[i][j] max(dp2[i][j], dp2[i - 1][j - sz[i]] val[i]);}}cout dp1[n][v] endl;cout (dp2[n][v] -1 ? 0 : dp2[n][v]) endl;return 0;
}我的思路
老师教的
对于第一问 状态表示dp[i][j]表示 i 位置之前的物品能够装入背包体积不大于 j 的最大价值 状态转移方程 如果不选 i 位置的物品 就要从 i - 1位置的物品中选择能够装入背包体积不大于 j 的最大价值 dp[i][j] dp[i - 1][j]; 如果选 i 位置 的物品 就要判断能不能选如果不能就选择前面的方案如果能选则我们选上当前位置的物品val[i]之后还要从 i - 1 位置的物品中选择体积不超过j - sz[i] 的最大价值最后吧这一种方案与前面一种方案取最大值即可 if(sz[i] j) dp[i][j] max(dp[i - 1][j], dp[i - 1][j - sz[i]] val[i]);
对于第二问 状态表示dp[i][j]表示位置之前的物品能够装入背包体积刚好等于 j 的最大价值 状态转移方程 如果不选 i 位置的物品 我们就要从 i - 1 位置中选出装入背包体积等于 j 的最大价值 dp[i][j] dp[i - 1][j]这和之前的状态转移方程是一样的因为状态表示变了 如果选 i 位置的物品我们仍然要判断能不能选此时还有一种情况就是存不存在可以选 i 位置物品的情况因为如果要使体积刚好等于 j 这种情况可能是不存在的所以要多加一个判断条件 if(sz[i] j dp2[i - 1][j - sz[i]] ! -1) dp[i][j] max(dp[i - 1][j], dp[i - 1][j - sz[i]] val[i])
注意dp2[i - 1][j - sz[i]] ! -1用-1判断是因为我们需要与0的意义区分开0表示dp[i][j]表示位置之前的物品能够装入背包体积刚好等于 j 的最大价值为0而不是没有这种情况只是价值为0而已
我的笔记: 还是要注意数组下标的映射关系这个比较容易出错不管是在输入数据、初始化、填表的时候 背包问题的思想 对于空间优化的建议 不要深究空间优化之后状态表示以及状态转移方程的实际含义空间优化重点是处理后面的填表中用不到的数据注意填表方式可能不同原因就是不能覆盖还需要的数据
分割等和子集
题目链接
分割等和子集
要点
问题核心判断数组是否能被分割成两个和相等的子集。关键在于找到子集和为总和的一半。数学条件若总和为奇数直接返回false若最大元素超过总和一半也直接返回false。动态规划定义dp[i][j]表示前i个元素是否能选出和为j的子集。
老师代码
class Solution
{
public:bool canPartition(vectorint nums){int n nums.size(), sum 0;for(auto x : nums) sum x;if(sum % 2) return false; // 如果不能平分直接返回 falseint aim sum / 2; // 定义⼀下⽬标值vectorvectorbool dp(n 1, vectorbool(aim 1)); // 建表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){dp[i][j] dp[i - 1][j];if(j nums[i - 1])dp[i][j] dp[i][j] || dp[i - 1][j - nums[i - 1]];}// 返回结果return dp[n][aim];}
}空间优化
class Solution
{
public:bool canPartition(vectorint nums){int n nums.size(), sum 0;for(auto x : nums) sum x;if(sum % 2) return false; // 如果不能平分直接返回 falseint aim sum / 2; // 定义⼀下⽬标值vectorbool dp(aim 1); // 建表dp[0] true; // 初始化for(int i 1; i n; i) // 填表for(int j aim; j nums[i - 1]; j--) // ⼀定要注意修改遍历顺序dp[j] dp[j] || dp[j - nums[i - 1]];// 返回结果return dp[aim];}
};老师思路
先将问题转化成我们「熟悉」的题型。
如果数组能够被分成两个相同元素之和相同的⼦集那么原数组必须有下⾯⼏个性质
i. 所有元素之和应该是⼀个偶数ii. 数组中最⼤的元素应该⼩于所有元素总和的⼀半iii. 挑选⼀些数这些数的总和应该等于数组总和的⼀半。
根据前两个性质我们可以提前判断数组能够被划分。根据最后⼀个性质我们发现问题就转化成了「01 背包」的模型
i. 数组中的元素只能选择⼀次ii. 每个元素⾯临被选择或者不被选择的处境iii. 选出来的元素总和要等于所有元素总和的⼀半。
其中数组内的元素就是物品总和就是背包。那么我们就可以⽤背包模型的分析⽅式来处理这道题。
请⼤家注意「不要背」状态转移⽅程因为题型变化之后状态转移⽅程就会跟着变化。我们要记住的是分析问题的模式。⽤这种分析问题的模式来解决问题 状态表⽰dp[i][j] 表⽰在前 i 个元素中选择所有的选法中能否凑成总和为 j 这个数 状态转移⽅程⽼规矩根据「最后⼀个位置」的元素结合题⽬的要求分情况讨论 i. 不选择 nums[i] 那么我们是否能够凑成总和为 j 就要看在前 i - 1 个元素中选能否凑成总和为 j 。根据状态表⽰此时 dp[i][j] dp[i - 1][j]ii. 选择 nums[i] 这种情况下是有前提条件的此时的 nums[i] 应该是⼩于等于 j 。因为如果这个元素都⽐要凑成的总和⼤选择它就没有意义呀。那么我们是否能够凑成总和为 j 就要看在前 i - 1 个元素中选能否凑成总和为 j - nums[i] 。根据状态表⽰此时 dp[i][j] dp[i - 1][j - nums[i]] 。 综上所述两种情况下只要有⼀种能够凑成总和为 j 那么这个状态就是 true 。因此状态转移⽅程为 dp[i][j] dp[i - 1][j] if(nums[i - 1] j) dp[i][j] dp[i][j] || dp[i - 1][j -nums[i]] 初始化由于需要⽤到上⼀⾏的数据因此我们可以先把第⼀⾏初始化。第⼀⾏表⽰不选择任何元素要凑成⽬标和 j 。只有当⽬标和为 0 的时候才能做到因此第⼀⾏仅需初始化第⼀个元素 dp[0][0] true 填表顺序根据「状态转移⽅程」我们需要「从上往下」填写每⼀⾏每⼀⾏的顺序是「⽆所谓的」。 返回值根据「状态表⽰」返回 dp[n][aim] 的值。 其中 n 表⽰数组的⼤⼩ aim 表⽰要凑的⽬标和。 空间优化所有的「背包问题」都可以进⾏空间上的优化。对于 01背包类型的我们的优化策略是 i. 删掉第⼀维ii. 修改第⼆层循环的遍历顺序即可。
我的代码
class Solution {
public:bool canPartition(vectorint nums) {int m nums.size();int sum 0;for(int i 0; i m; i)sum nums[i];if(sum % 2) return false;//如果数组和为一个奇数则他一定不能分成两个相等的整数int k sum / 2;vectorvectorbool dp(m 1, vectorbool(k 1));//初始化for(int i 0; i m; i) dp[i][0] true;//填表for(int i 1; i m; i){for(int j 0; j k; j){dp[i][j] dp[i - 1][j];if(j - nums[i - 1] 0) dp[i][j] dp[i][j] || dp[i - 1][j - nums[i - 1]];}}return dp[m][k];}
};空间优化
class Solution {
public:bool canPartition(vectorint nums) {int m nums.size();int sum 0;for(int i 0; i m; i)sum nums[i];if(sum % 2) return false;int k sum / 2;vectorbool dp(k 1);//初始化dp[0] true;//填表for(int i 1; i m; i){for(int j k; j 0; j--){if(j - nums[i - 1] 0) dp[j] dp[j] || dp[j - nums[i - 1]];}}return dp[k];}
};我的思路
将问题转化为“是否存在子集和为sum/2”转化为01背包问题。初始化dp[0][0] true空集和为0其他dp[0][j] falsej 0时无法用空集凑出。
我的笔记:
如何将这一个问题转化为01背包问题数组下标映射关系为什么要多开一行一列的dp空间因为当我们不选也就是子集为空以及和为0的情况是有研究价值的也就是会出现这种情况的
目标和
题目链接
目标和
要点
问题转化设正数和为a负数和为b则a - b target且a b sum推导得a (sum target) / 2。合法性判断若(sum target)为奇数或target绝对值超过sum直接返回0
老师代码
class Solution
{
public:int findTargetSumWays(vectorint nums, int target){int sum 0;for(auto x : nums) sum x;int aim (sum target) / 2;// 处理⼀下边界条件if(aim 0 || (sum target) % 2) return 0;int n nums.size();vectorvectorint dp(n 1, vectorint(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];}
}老师思路
本题可以直接⽤「暴搜」的⽅法解决。但是稍微⽤数学知识分析⼀下就能转化成我们常⻅的「背包模型」的问题。
设我们最终选取的结果中前⾯加 号的数字之和为 a 前⾯加 - 号的数字之和为 b 整个数组的总和为 sum 于是我们有
a b sum
a - b target
上⾯两个式⼦消去 b 之后可以得到 a (sum target) / 2 也就是说我们仅需在 nums 数组中选择⼀些数将它们凑成和为 (sum target) / 2 即可。问题就变成了 416. 分割等和⼦集 这道题。 我们可以⽤相同的分析模式来处理这道题 状态表⽰dp[i][j] 表⽰在前 i 个数中选总和正好等于 j ⼀共有多少种选法。 状态转移⽅程⽼规矩根据「最后⼀个位置」的元素结合题⽬的要求我们有「选择」最后⼀个元素或者「不选择」最后⼀个元素两种策略 i. 不选 nums[i] 那么我们凑成总和 j 的总⽅案就要看在前 i - 1 个元素中选凑成总和为 j 的⽅案数。根据状态表⽰此时 dp[i][j] dp[i - 1][j] ii. 选择 nums[i] 这种情况下是有前提条件的此时的 nums[i] 应该是⼩于等于 j 。因为如果这个元素都⽐要凑成的总和⼤选择它就没有意义呀。那么我们能够凑成总和为 j 的⽅案数就要看在前 i - 1 个元素中选能否凑成总和为 j - nums[i] 。根据状态表⽰此时 dp[i][j] dp[i - 1][j - nums[i]] 综上所述两种情况如果存在的话应该要累加在⼀起。因此状态转移⽅程为dp[i][j] dp[i - 1][j] if(nums[i - 1] j) dp[i][j] dp[i][j] dp[i - 1][j - nums[i- 1]] 初始化由于需要⽤到「上⼀⾏」的数据因此我们可以先把第⼀⾏初始化。第⼀⾏表⽰不选择任何元素要凑成⽬标和 j 。只有当⽬标和为 0 的时候才能做到因此第⼀⾏仅需初始化第⼀个元素 dp[0][0] 1 填表顺序根据「状态转移⽅程」我们需要「从上往下」填写每⼀⾏每⼀⾏的顺序是「⽆所谓的」。 返回值根据「状态表⽰」返回 dp[n][aim] 的值。 其中 n 表⽰数组的⼤⼩ aim 表⽰要凑的⽬标和 空间优化所有的「背包问题」都可以进⾏空间上的优化。对于 01背包类型的我们的优化策略是 i. 删掉第⼀维ii. 修改第⼆层循环的遍历顺序即可
我的代码
class Solution
{
public:int findTargetSumWays(vectorint nums, int target) {int m nums.size();int sum 0;for(auto n : nums) sum n;if((sum target) % 2) return 0;//如果是奇数则一定不存在一种情况使int k (sum target) / 2;//如果k的值小于0这种情况下是找不到的因为题目给了nums中的数是大于0的if(k 0) return 0;vectorvectorint dp(m 1, vectorint(k 1));//初始化dp[0][0] 1;//填表for(int i 1; i m; i){for(int j 0; j k; j)//这里要从0开始因为按照题目要求nums[i]可能为0{ dp[i][j] dp[i - 1][j];if(j - nums[i - 1] 0) dp[i][j] dp[i][j] dp[i - 1][j - nums[i - 1]];}}return dp[m][k];}
};空间优化
class Solution
{
public:int findTargetSumWays(vectorint nums, int target) {int m nums.size();int sum 0;for(auto n : nums) sum n;if((sum target) % 2) return 0;//如果是奇数则一定不存在一种情况使int k (sum target) / 2;if(k 0) return 0;vectorint dp(k 1);//初始化dp[0] 1;//填表for(int i 1; i m; i){for(int j k; j - nums[i - 1] 0; j--){dp[j] dp[j - nums[i - 1]];}}return dp[k];}
};我的思路
使用动态规划统计组成和为a的方案数状态转移方程为 dp[j] dp[j - nums[i]]若j nums[i]。初始化dp[0] 1表示空集和为0的方案数为1。
我的笔记: 注意边界条件包括sum target的值不能为奇数因为k涉及除法可能存在除不尽的问题以及k的值不能小于0nums[i]都是大于0的数 要看清题目要求 原始数组与dp表的下标映射关系
最后一块石头的重量II
题目链接
最后一块石头的重量II
要点
问题转化将石头粉碎过程转化为对数组元素赋予正负号使得两部分的差值最小。最终结果等价于求数组分割成两个子集的最小差值。数学推导设总和为sum理想分割为两子集和接近sum/2差值最小为sum - 2*max_subset_sum。状态转移优化用01背包求不超过sum/2的最大子集和直接计算最终差值。
老师代码
class Solution
{
public:int lastStoneWeightII(vectorint stones){// 1. 准备⼯作int sum 0;for(auto x : stones) sum x;int n stones.size(), m sum / 2;// 2. dpvectorvectorint dp(n 1, vectorint(m 1));for(int i 1; i n; i)for(int j 0; j m; j){dp[i][j] dp[i - 1][j];if(j stones[i - 1])dp[i][j] max(dp[i][j], dp[i - 1][j - stones[i - 1]] stones[i - 1]);}// 3. 返回结果return sum - 2 * dp[n][m];}
}老师思路
先将问题「转化」成我们熟悉的题型。▪ 任意两块⽯头在⼀起粉碎重量相同的部分会被丢掉重量有差异的部分会被留下来。那就相当于在原始的数据的前⾯加上「加号」或者「减号」是最终的结果最⼩即可。也就是说把原始的⽯头分成两部分两部分的和越接近越好。▪ ⼜因为当所有元素的和固定时分成的两部分越接近数组「总和的⼀半」两者的差越⼩。因此问题就变成了在数组中选择⼀些数让这些数的和尽量接近 sum / 2 如果把数看成物品每个数的值看成体积和价值问题就变成了「01 背包问题」
我的代码
class Solution {
public:int lastStoneWeightII(vectorint stones) {int m stones.size();int sum 0;for(auto s : stones) sum s;int k sum / 2;vectorvectorint dp(m 1, vectorint(k 1));//填表for(int i 1; i m; i){for(int j 0; j k; j){dp[i][j] dp[i - 1][j];if(j - stones[i - 1] 0) dp[i][j] max(dp[i][j], dp[i - 1][j - stones[i - 1]] stones[i - 1]);}}return sum - 2 * dp[m][k];}
};我的思路 1.两个石头相撞结果要么为x-y要么为y-x 2.无论你怎么两两相碰永远有的数字前为正号有的为负号,因此你总可以把最终式化为一堆和减去另外一堆数字和 3.因此我们要找的是这个集合的两个子集之和的最小差 4.要想子集之和差最小则两者应该尽量接近或者相等 5.这个时候我们就可以把sum/2作为背包容量使用01背包来解题了
我的笔记:
若总和为奇数sum/2向下取整不影响结果因为差值只关心两部分的和差距。空间优化时内层循环需逆序遍历防止覆盖未使用的上一状态
解决01背包问题的注意事项
C语法细节
数组下标设计 从1开始存储物品信息避免处理i-1的边界问题如nums[i-1]对应第i个物品。二维dp表可优化为一维数组但需逆序更新防止覆盖。 数据类型选择 若结果可能较大如目标和方案数使用long long避免溢出。vector初始化时默认值需根据问题设定如-1表示非法状态0或1表示初始方案数。 空间优化实现 一维dp数组更新时内层循环必须逆序从大到小保证每个物品只选一次。初始化需单独处理dp[0]如dp[0] 1目标和问题或dp[0] 0最大价值问题。
算法思路核心
状态定义 明确dp[i][j]的含义例如“前i个物品中选出体积不超过j的最大价值”或“组成和为j的方案数”。 状态转移方程 分“选”与“不选”两种情况讨论注意合法性判断如体积不足时不能选。累加或取最大值需根据问题目标调整。 边界条件处理 初始化时dp[0][0]通常有特殊含义如空集和为0其他位置根据问题设定初始值。处理负值或非法状态如dp[j] -1表示无法凑出体积j。 问题转化技巧 将复杂问题转化为背包模型如“分割等和子集”转化为求子集和等于sum/2。利用数学公式简化问题如“目标和”中推导出a (sum target)/2。
