算法沉淀——动态规划之01背包问题
01.【模板】01背包02.分割等和子集03.目标和04.最后一块石头的重量 II
01背包问题是一类经典的动态规划问题，通常描述为：有一个固定容量的背包，以及一组物品，每件物品都有重量和价值，目标是找到在背包容量范围内，使得背包中的物品总价值最大的组合。
具体来说，问题的输入包括：
一个固定容量的背包（通常表示为一个整数W）。一组物品，每个物品有两个属性：重量（通常表示为一个整数weight）和价值（通常表示为一个整数value）。求解的目标是找到一种放置物品的方式，使得放入背包的物品的总重量不超过背包容量，并且总价值最大。
这个问题的特点是，对于每件物品，你只能选择将其放入背包一次（0-1，因此称为“01背包”），或者不放入背包。不能将物品切割成更小的部分放入背包，要么整个物品放入背包，要么不放入。
动态规划解法：
定义状态： 通常使用二维数组dp[i][j]表示在前i个物品中，背包容量为j时的最大总价值。 状态转移方程： 考虑第i个物品，可以选择放入背包或者不放入。如果选择放入，那么总价值为dp[i-1][j-weight[i]] + value[i]，即前i-1个物品的总价值加上当前物品的价值。如果选择不放入，那么总价值为dp[i-1][j]，即前i-1个物品的总价值。因此，状态转移方程为： dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
其中，dp[i-1][j]表示不放入第i个物品，dp[i-1][j-weight[i]] + value[i]表示放入第i个物品。 初始条件： 当i=0时，表示前0个物品，总价值为0；当j=0时，表示背包容量为0，总价值也为0。 遍历顺序： 外层循环遍历物品，内层循环遍历背包容量。 返回结果： 最终结果存储在dp[N][W]中，其中N为物品数量，W为背包容量。
例子：
假设有如下物品：
Copy code解释物品1：重量=2，价值=3
物品2：重量=3，价值=4
物品3：重量=4，价值=5
物品4：重量=5，价值=6
背包容量为W=8，我们要求解在这个条件下的最大总价值。
按照上述动态规划解法，构建状态转移表如下：
luaCopy code解释 重量/价值 0 1 2 3 4 5 6 7 8
----------------------------------------------
物品0 0 0 0 0 0 0 0 0 0
物品1 0 0 3 3 3 3 3 3 3
物品2 0 0 3 4 4 7 7 7 10
物品3 0 0 3 4 4 7 8 8 11
物品4 0 0 3 4 4 7 8 9 11
因此，最终结果为dp[4][8] = 11，表示在背包容量为8的情况下，最大总价值为11。这意味着最优解是选择物品2和物品4放入背包。
01.【模板】01背包
题目链接：https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
你有一个背包，最多能容纳的体积是V。
现在有n个物品，第i个物品的体积为vi,价值为wi。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数vi和wi，表示第i个物品的体积和价值。
1≤n,V;vi,wi≤1000
输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
示例1
输入：
3 5
2 10
4 5
1 4
输出：
14
9
复制
说明：
装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。
示例2
输入：
3 8
12 6
11 8
6 8
输出：
8
0
说明：
装第三个物品时总价值最大但是不满，装满背包无解。 要求O(nV)的时间复杂度，O(V)空间复杂度
思路
第一问：
状态表示：
dp[i][j] 表示从前 i 个物品中挑选，总体积不超过 j 的情况下，所有的选法中能挑选出的最大价值。 状态转移方程：
对于每个物品，我们有两种选择：
不选第 i 个物品：此时 dp[i][j] = dp[i - 1][j]。选择第 i 个物品：此时需要确保总体积不超过 j - v[i]，而且该状态是合法的，即 j >= v[i] 和 dp[i - 1][j - v[i]] 存在。状态转移方程为 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])。 初始化：
多加一行，第一行初始化为 0，因为不选任何物品总体积为 0时，价值为 0。 填表顺序：
从上往下，每一行从左往右填表。 返回值：
返回 dp[n][V]，即最后一行最后一列的值。
第二问：
状态表示：
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]] 是否为 -1。 初始化：
多加一行，第一格初始化为 0，表示正好凑齐体积为 0的背包。第一行后面的格子初始化为 -1，因为没有物品，无法满足体积大于 0的情况。 填表顺序：
从上往下，每一行从左往右填表。 返回值：
由于最后可能凑不成体积为 V 的情况，需要特判。
代码
#include
#include
#include
using namespace std;
const int N=1002;
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< 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])< } 优化步骤： 滚动数组的应用： 在01背包问题中，通过滚动数组可以删去所有的横坐标，因为状态 dp[i][j] 只依赖于上一行的状态 dp[i-1][j] 和 dp[i-1][j-v[i]]，因此只需保留一行状态。 遍历顺序修改： 修改了 j 的遍历顺序，原本的遍历是从 0 到 V，现在改为从 V 到 0。这样做的原因是，如果从 0 到 V 遍历，会使用当前行的 dp[i-1][j-v[i]] 的值，而我们已经在上一步的滚动数组中删除了这一行，所以需要改变遍历顺序，从 V 到 0。 #include #include #include using namespace std; const int N=1002; 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< 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])< } 02.分割等和子集 题目链接：https://leetcode.cn/problems/partition-equal-subset-sum/ 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 示例 1： 输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2： 输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。 提示： 1 <= nums.length <= 2001 <= nums[i] <= 100 思路 状态表达： dp[i][j] 表示在前 i 个元素中选择，所有的选法中，能否凑成总和为 j 这个数。 状态转移方程： 根据最后一个位置的元素，分两种情况讨论： 不选择 nums[i]：此时是否能够凑成总和为 j 取决于前 i-1 个元素的情况，即 dp[i][j] = dp[i-1][j]。选择 nums[i]：如果 nums[i] 小于等于 j，则需要看前 i-1 个元素中是否能凑成总和为 j - nums[i]，即 dp[i][j] = dp[i][j] || dp[i-1][j - nums[i]]。 初始化： 第一行表示不选择任何元素，要凑成目标和 j，只有当目标和为 0 时才能做到，因此第一行仅需初始化第一个元素 dp[0][0] = true。 填表顺序： 根据状态转移方程，从上往下填写每一行，每一行的顺序是无所谓的。 返回值： 根据状态表达，返回 dp[n][aim] 的值，其中 n 表示数组的大小， aim 表示要凑的目标和。 空间优化： 对于 01 背包类型的问题，可以进行空间上的优化，即删除第一维，并修改第二层循环的遍历顺序。 代码 class Solution { public: bool canPartition(vector int n=nums.size(),sum=0; for(int x:nums) sum+=x; if(sum%2) return false; int aim=sum/2; vector 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(vector int n=nums.size(),sum=0; for(int x:nums) sum+=x; if(sum%2) return false; int aim=sum/2; vector 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]; } }; 03.目标和 题目链接：https://leetcode.cn/problems/target-sum/ 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 示例 1： 输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3 示例 2： 输入：nums = [1], target = 1 输出：1 提示： 1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000 思路 状态表示： dp[i][j] 表示在前 i 个数中选，总和正好等于 j，一共有多少种选法。 状态转移方程： 根据最后一个位置的元素，结合题目的要求，有两种策略： 不选 nums[i]：此时凑成总和 j 的总方案数，要看在前 i-1 个元素中选，凑成总和为 j 的方案数，即 dp[i][j] = dp[i-1][j]。选择 nums[i]：如果 nums[i] 小于等于 j，则需要看前 i-1 个元素中是否能凑成总和为 j - nums[i]，即 dp[i][j] += dp[i-1][j - nums[i]]。 初始化： 需要用到上一行的数据，因此初始化第一行，表示不选择任何元素凑成目标和 j。只有当目标和为 0 时才能做到，因此第一行仅需初始化第一个元素 dp[0][0] = 1。 填表顺序： 根据状态转移方程，从上往下填写每一行，每一行的顺序是无所谓的。 返回值： 根据状态表示，返回 dp[n][aim] 的值，其中 n 表示数组的大小， aim 表示要凑的目标和。 代码 class Solution { public: int findTargetSumWays(vector 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(); vector 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]; } }; 04.最后一块石头的重量 II 题目链接：https://leetcode.cn/problems/last-stone-weight-ii/ 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下： 如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。 示例 1： 输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。 示例 2： 输入：stones = [31,26,33,21,40] 输出：5 提示： 1 <= stones.length <= 301 <= stones[i] <= 100 思路 状态表示： dp[i][j] 表示在前 i 个元素中选择，总和不超过 j 的情况下，这些元素的最大和。 状态转移方程： 根据最后一个位置的元素，结合题目的要求，有两种策略： 不选 stones[i]：此时是否能够凑成总和为 j，要看在前 i-1 个元素中选，能否凑成总和为 j。根据状态表示，此时 dp[i][j] = dp[i-1][j]。选择 stones[i]：这种情况下是有前提条件的，此时的 stones[i] 应该是小于等于 j。因为如果这个元素都比要凑成的总和大，选择它就没有意义。那么是否能够凑成总和为 j，要看在前 i-1 个元素中选，能否凑成总和为 j - stones[i]。根据状态表示，此时 dp[i][j] = dp[i-1][j-stones[i]] + stones[i]。 初始化： 由于需要用到上一行的数据，可以先将第一行初始化。第一行表示「没有石头」，因此想凑成目标和 j 的最大和都是 0。 填表顺序： 根据状态转移方程，从上往下填写每一行，每一行的顺序是无所谓的。 返回值： 根据状态表示，找到最接近 sum / 2 的最大和 dp[n][sum / 2]。返回 sum - 2 * dp[n][sum / 2]，因为我们要的是两堆石头的差。 代码 class Solution { public: int lastStoneWeightII(vector int sum=0; for(int x:stones) sum+=x; int n=stones.size(),m=sum/2; vector 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]); } return sum-2*dp[n][m]; } }; 文章来源
您阅读本篇文章共花了：
发表评论