当前位置：首页 > news >正文

01背包类问题

news 来源：原创 2025/8/3 22:30:58

文章目录

[模版]01背包
- 1. 第一问: 背包不一定能装满
- - (1) 状态表示
  - (2) 状态转移方程
  - (3) 初始化
  - (4) 填表顺序
  - (5) 返回值
- 2. 第二问: 背包恰好装满
- 3. 空间优化
416.分割等和子集
- 1. 状态表示
- 2. 状态转移方程
- 3. 初始化
- 4. 填表顺序
- 5. 返回值
[494. 目标和](https://leetcode.cn/problems/target-sum/description/)
- 1. 状态表示
- 2. 状态转移方程
- 3. 初始化
- 4. 填表顺序
- 5. 返回值
1049.最后一块石头的重量II
- 1. 状态表示
- 2. 状态转移方程
- 3. 初始化
- 4. 填表顺序
- 5. 返回值

[模版]01背包

1. 第一问: 背包不一定能装满

(1) 状态表示

dp[i][[j]: 从前 i 个物品中挑选, 总体积不超过 j, 所有选法中, 能挑选出来的最大价值.

(2) 状态转移方程

根据最后一步的状况, 分情况讨论:

不选 i 物品
此时就是在前 i-1 个物品中挑选, 总体积不超过 j, 所有选法中, 能挑选出来的最大价值.

dp[i][j] = dp[i-1][j]

选 i 物品
选了 i 物品, 说明最后要加上 w[i], 此时就是在前 i-1 个物品中挑选, 总体积不超过 j - v[i], 所有选法中, 能挑选出来的最大价值.

dp[i][j] = dp[i-1][ j - v[i] ] + w[i]

注:j-v[i]可能不存在, 所以 j-v[i] >= 0
比如, j = 1, 但是 v[i] = 4 了, 此时 j-v[i] 为负数了, 就是不存在的.

综上, 状态转移方程为:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])

(3) 初始化

根据题意可知, 下标是从 1 开始的, 所以 dp表会多一行多一列.
横坐标代表物品数, 纵坐标代表体积.
第0行表示: 从前0个物品中挑选, 总体积不超过 j 的最大价值, 就是为0.
第0列表示: 从前 i 个物品中挑选, 总体积不超过 0 的最大价值, 物品都是有体积的, 这种情况也不存在, 也是为0.

所以可以不用特别的初始化, 默认为0即可.

(4) 填表顺序

从上往下

(5) 返回值

根据状态表示可知, 题目最终要返回的是, 从前 n 个物品中挑选, 总体积不超过 v 的最大价值.
即返回: dp[n][v].

2. 第二问: 背包恰好装满

与第一问的讨论思路和过程是一模一样, 状态转移方程也一样, 只有以下几点有细微的变化:

(1) 状态表示
dp[i][[j]: 从前 i 个物品中挑选, 总体积恰好等于 j, 所有选法中, 能挑选出来的最大价值.

(2) 判断状态方程是否存在
在求每一个状态时, 从前 i-1 个物品中选,可能会选不出体积恰好等于 j 的物品.
此时可以做一个约定: dp[i][j] = -1时, 表示没有这种情况.
其实在第一种情况不选 i 物品时, 是可以不用特判 dp[i-1][j] != -1的. 因为第一种情况不选 i 物品是一定存在的, 如果 dp[i-1][j] = -1, 那么 dp[i][j] = -1, 这是合理的.
但是第二种情况选 i 物品时一定要特判 dp[i-1][j-v[i]] != -1. 因为第二种情况多加了一个 w[i], 如果 dp[i-1][j-v[i]] 等于 -1, 再加上 w[i], 就会影响最终结果了.

(3) 初始化
第一个格子为0 , 因为正好能凑齐体积为0 的背包, 但是第一行后面的格子都是 -1 , 因为没有物品, 无法满足体积大于 0 的情况.

(4) 返回值
最后有可能凑不出体积恰好为 V 的,所以返回之前要特判一下.

代码实现如下:

#include <iostream>
#include <cstring>
using namespace std;const int N = 1010;
int n, V;
int v[N], w[N];
int dp[1010][1010];int main()
{cin >> n >> V;for(int i = 1; i <= n; i++) //下标从1开始cin >> v[i] >> w[i];//解决第一问for(int i = 1; i <= n; i++){for(int j = 1; j <= V; j++){dp[i][j] = dp[i-1][j];if(j - v[i] >= 0)dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);}}cout << dp[n][V] << endl;//解决第二问memset(dp, 0, sizeof(dp));for(int i = 1; i <= V; i++)dp[0][i] = -1;for(int i = 1; i <= n; i++){for(int j = 1; j <= V; j++){dp[i][j] = dp[i-1][j];// 注意要特判if(j - v[i] >= 0 && dp[i-1][j-v[i]] != -1)dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);}}cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;return 0;
}

3. 空间优化

1.利用滚动数组做空间上的优化
2.直接在原始的代码上修改即可
步骤:

1.把二维dp表中的 i (所有横坐标)去掉改成一维(不是改成一层循环,还是需要两层循环,只是把dp表中的 i 去掉).
2.修改 j 的遍历顺序成从右往左.

修改后的代码如下:

#include <iostream>
#include <cstring>
using namespace std;const int N = 1010;
int n, V;
int v[N], w[N];
int dp[1010];int main()
{cin >> n >> V;for(int i = 1; i <= n; i++) //下标从1开始cin >> v[i] >> w[i];//解决第一问for(int i = 1; i <= n; i++){for(int j = V; j >= 0; j--){dp[j] = dp[j];if(j - v[i] >= 0)dp[j] = max(dp[j], dp[j-v[i]] + w[i]);}}cout << dp[V] << endl;//解决第二问memset(dp, 0, sizeof(dp));for(int i = 1; i <= V; i++)dp[i] = -1;for(int i = 1; i <= n; i++){for(int j = V; j >= 0; j--){dp[j] = dp[j];// 注意要特判if(j - v[i] >= 0 && 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;
}

416.分割等和子集

1. 状态表示

dp[i][j]:从前 i 个数中选,和是否恰好等于 j ,是为true, 不是为false.

2. 状态转移方程

和01背包问题一样, 根据第 i 个位置选或不选,分两种情况讨论:
(1) 不选第 i 个数: dp[i][j] = dp[i-1][j]
(2) 选第 i 个数: dp[i][j] = dp[i-1][j-nums[i]]
只要这两种选法中有一个能凑成就是符合题意的, 所以可得:
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
注意: j - nums[i] >= 0.

3. 初始化

为了防止填表时出现越界问题,一般还是多开一行多开一列.
(0, 0) 位置, 从前 0 个数中选,和是否恰好等于 0, 成立, 所以是 true, 第一行的其他位置则为 false.
第一列, 从前 i 个数中选,和是否恰好等于 0, 成立, 所以第一列初始化为 true.

4. 填表顺序

从上往下.

5. 返回值

本题可以转化为: 在数组中选一些数, 让这些数的和等于 sum / 2.(其中sum是整个数组的和).
所以最终返回: dp[n][sum / 2] 即可.

代码实现如下:

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();int sum = 0;for(auto x : nums) sum += x;//当和为奇数时,不能等和分if(sum % 2 == 1) return false;vector<vector<bool>>dp(n+1, vector<bool>(sum+1));for(int j = 1; j <= sum; j++) dp[0][j] = false;for(int i = 0; i <= n; i++) dp[i][0] = true;for(int i = 1; i <= n; i++){for(int j = 1; j <= sum; j++){dp[i][j] = dp[i-1][j];if(j - nums[i-1] >= 0)dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];}}return dp[n][sum/2];}
};

空间优化后的代码如下:

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();int sum = 0;for(auto x : nums) sum += x;if(sum % 2 == 1) return false;vector<bool>dp(vector<bool>(sum+1));for(int j = 1; j <= sum; j++) dp[j] = false;for(int i = 0; i <= n; i++) dp[0] = true;for(int i = 1; i <= n; i++){for(int j = sum; j >= 1; j--){dp[j] = dp[j];if(j - nums[i-1] >= 0)dp[j] = dp[j] || dp[j-nums[i-1]];}}return dp[sum/2];}
};

494. 目标和

我们先对这道题进行分析:
在添加完±号后会有正数和负数,我们把所有正数和记为a,所有负数和的绝对值记为b,总和记为sum.
根据题意可知: a-b=target, a+b=sum,可得 a = (sum+target)/2

所以原题可转换为:在数组中选一些数，让这些数字的和等于a，一共有多少种选法.
这就是一个01背包问题, 下面的分析过程和上一题 [416.分割等和子串] 基本一样.

1. 状态表示

dp[i][j]:从前 i 个数中选，使得总和为 j ，一共有多少种选法.

2. 状态转移方程

根据i位置的状态，有两种情况：
1.i 位置不选，dp[i][j] = dp[i-1][j]
2.i 位置选，dp[i][j] = dp[i-1][j-nums[i]]
注意: j >= nums[i].
综上，两种选法的总数:
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]

3. 初始化

依旧是多加一行多加一列.
第一行:数组里没有元素，要凑成和为0,和为1… 都凑不出, 所以填 0, 但是 dp[0][0] = 1.
第一列:除了第一个位置，其余位置是可以不用特别初始化的.
因为本题的数字有可能是0,第一列表示的是从前 i 个数字中，总和为0的选法,那就会有很多种情况了。
而我们初始化的目的就是避免填表时越界访问，而选第 i 个位置时，是用第二种情况,这种情况我们有前提条件 j >= nums[i]，当 j = 0 时, 要使用那个方程就要满足 nums[i] = 0, 此时 dp[i][j] = dp[i-1][0], 这使得这种情况填表时只会使用表中的上一个位置，而不是越界访问。
![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/04948e2307da45a3a6d4ba01722ca7b6.png

4. 填表顺序

从上往下

5. 返回值

根据我们上面的分析可知, 最终返回: dp[n][a] 即可.

代码实现如下:

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

空间优化后的代码如下:

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

1049.最后一块石头的重量II

我们先来分析题目:
挑选两个石头粉碎，其实就是在任意两个石头前添加±号
分析思路同"目标和"一题，全部正数和记为a,负数和绝对值记为b. 要求的就是|a-b|的最小值。
而我们又知道全部数的总和sum, 即a+b=sum.
求|a-b|的最小值可以说成: 把一个数sum拆成两个数，求这两个数的差的最小值.
而只有当这两个数越接近sum/2时，差就越小
综上分析，本题可转换为:
在数组中选择一些数，让这些数的和尽可能接近sum/2("这些数的和"就是上面的a或b).

本质就是一个01背包问题:
物品 - 数
每个物品的价值 - nums[i]
每个物品体积 - nums[i]
背包体积 - sum/2.
选一些数放进背包中，在不超过背包体积的情况下，里面的最大和是多少.

1. 状态表示

dp[i][j]:从前i个数中选，总和不超过j,此时的最大和.

2. 状态转移方程

根据i位置的状态，有两种情况：
1.i 位置不选，dp[i][j] = dp[i-1][j]
2.i 位置选，dp[i][j] = dp[i-1][j-nums[i]] + nums[i]
注意: j >= nums[i].
综上: dp[i][j] = max(dp[i-1][j] , dp[i-1][j-nums[i]])

3. 初始化

多一行多一列
第一行:背包中没有石头，无法凑成总和为0,1,2,3… 初始化为0即可
第一列:同 [目标和] 一题.

4. 填表顺序

从上往下

5. 返回值

dp[n][sum/2] 就是上面分析中的 a，则 b = sum-dp[n][sum/2], 所以最小值为 a - b = sum - 2 * dp[n][sum/2].

代码实现如下:

class Solution 
{
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size(), sum = 0;for(auto x : stones) sum += x;vector<vector<int>> dp(n+1, vector<int>(sum / 2 + 1));for(int i = 1; i <= n; i++){for(int j = 0; j <= sum / 2; j++){dp[i][j] = dp[i-1][j];if(j >= stones[i-1])dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i-1]] + stones[i-1]);}}// dp[n][sum/2]就是上面分析中的a，则b=sum-dp[n][sum/2]// 所以最小值为a-b=sum - 2 * dp[n][sum/2]return sum - 2 * dp[n][sum/2];}
};

空间优化后的代码:

class Solution 
{
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size(), sum = 0;for(auto x : stones) sum += x;vector<int> dp(vector<int>(sum / 2 + 1));for(int i = 1; i <= n; i++){for(int j = sum / 2; j >= 1; j--){dp[j] = dp[j];if(j >= stones[i-1])dp[j] = max(dp[j], dp[j-stones[i-1]] + stones[i-1]);}}// dp[n][sum/2]就是上面分析中的a，则b=sum-dp[n][sum/2]// 所以最小值为a - b = sum - 2 * dp[sum/2]return sum - 2 * dp[sum/2];}
};

文章目录

1. 第一问: 背包不一定能装满

(1) 状态表示

(2) 状态转移方程

(3) 初始化

(4) 填表顺序

(5) 返回值

2. 第二问: 背包恰好装满

3. 空间优化

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

相关文章：