代码训练营DAY35 第九章 动态规划part03

动态规划：01背包理论基础

46. 携带研究材料（第六期模拟笔试）

01背包原理

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动规五部曲

1. 确定dp数组以及下标的含义

我们需要使用二维数组，为什么呢？

因为有两个维度需要分别表示：物品 和 背包容量

i 、j、dp[i][j] 分别表示什么呢？i 来表示物品、j表示背包容量。

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2. 确定递推公式

对于递推公式，首先我们要明确有哪些方向可以推导出 dp[i][j]。

求取 dp[1][4] 有两种情况：

1. 放物品1
2. 还是不放物品1
3. 如果放物品1， 那么背包要先留出物品1的容量，目前容量是4，物品1 的容量（就是物品1的重量）为3，此时背包剩下容量为1。

4. 容量为1，只考虑放物品0 的最大价值是 dp[0][1]，这个值我们之前就计算过。

   所以 放物品1 的情况 = dp[0][1] + 物品1 的价值，推导方向如图：

递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. dp数组如何初始化

初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

有递归公式，可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。

当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

dp[i][j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。

4. 确定遍历顺序

先遍历 物品还是先遍历背包重量呢？

其实都可以！！ 但是先遍历物品更好理解。

5、举例推导

#include <bits/stdc++.h>
using namespace std;int main(){int n,bagweight;cin>>n>>bagweight;vector<int> weight(n,0);vector<int> value(n,0);for(int i=0;i<n;i++){cin>>weight[i];}for(int j=0;j<n;j++){cin>>value[j];}vector<vector<int>> dp(weight.size(),vector<int>(bagweight+1,0));for(int j=weight[0];j<=bagweight;j++){dp[0][j]=value[0];}for(int i=1;i<n;i++){for(int j=0;j<=bagweight;j++){if(j<weight[i]) dp[i][j]=dp[i-1][j];else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);}}}cout<<dp[n-1][bagweight]<<endl;return 0;
}

动态规划：01背包理论基础（滚动数组）

46. 携带研究材料（第六期模拟笔试）

一维dp数组（滚动数组）

1、确定dp数组的定义

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2、一维dp数组的递推公式

递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3、一维dp数组如何初始化

dp[0]=0；其他的也设为0

4、一维dp数组遍历顺序

倒序遍历是为了保证物品i只被放入一次！只能先遍历物品嵌套遍历背包容量。

5、举例推导dp数组

#include <iostream>
#include <vector>
using namespace std;int main(){int n,bagweight;cin>>n>>bagweight;vector<int> weight(n,0);vector<int> value(n,0);for(int i=0;i<n;i++){cin>>weight[i];}for(int j=0;j<n;j++){cin>>value[j];}vector<int> dp(bagweight + 1,0);for(int i=0;i<n;++i){for(int j=bagweight;j>=weight[i];--j){dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);}}cout<<dp[bagweight]<<endl;return 0;
}

416. 分割等和子集

 416. 分割等和子集 - 力扣（LeetCode）

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1:

• 输入: [1, 5, 11, 5]
• 输出: true
• 解释: 数组可以分割成 [1, 5, 5] 和 [11].

只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。回溯暴力搜索出所有答案的，但最后超时了，这是 背包算法可以解决的经典类型题目。

动规五部曲

1. 确定dp数组以及下标的含义

dp[j] 表示： 容量（所能装的重量）为j的背包，所背的物品价值最大可以为dp[j]。

2. 确定递推公式

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

3. dp数组如何初始化

dp[0]一定是0，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

4. 确定遍历顺序

物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

for(int i = 0; i < nums.size(); i++) {for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}
}

5. 举例推导dp数组

用例1，输入[1,5,11,5] 为例，如图：

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