01背包类问题

[模版]01背包

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

(1) 状态表示

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

(2) 状态转移方程

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

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

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

2. 选 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], 这使得这种情况填表时只会使用表中的上一个位置，而不是越界访问。

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];}
};