动态规划part03
文章参考来源代码随想录
题目参考来源leetcode
01背包问题 二维：
背包问题：
动规五部曲：
1.确定dp数组以及下标的含义：
其实这里由题目要我们求的就可以推出来了
把下标为0-i的物品装入容量为j的背包最大价值为dp[i][j]。
具体分析：
我们需要使用二维数组，为什么呢？
因为有两个维度需要分别表示：物品 和 背包容量
如图，二维数组为 dp[i][j]。
那么这里 i 、j、dp[i][j] 分别表示什么呢？
i 来表示物品、j表示背包容量。
我们来尝试把上面的 二维表格填写一下。
动态规划的思路是根据子问题的求解推导出整体的最优解。
我们先看把物品0 放入背包的情况：
背包容量为0，放不下物品0，此时背包里的价值为0。
背包容量为1，可以放下物品0，此时背包里的价值为15.
背包容量为2，依然可以放下物品0 （注意 01背包里物品只有一个），此时背包里的价值为15。
以此类推。
再看把物品1 放入背包：
背包容量为 0，放不下物品0 或者物品1，此时背包里的价值为0。
背包容量为 1，只能放下物品0，背包里的价值为15。
背包容量为 2，只能放下物品0，背包里的价值为15。
背包容量为 3，上一行同一状态，背包只能放物品0，这次也可以选择物品1了，背包可以放物品1 或者 物品0，物品1价值更大，背包里的价值为20。
背包容量为 4，上一行同一状态，背包只能放物品0，这次也可以选择物品1了，背包可以放下物品0 和 物品1，背包价值为35。
以上举例，是比较容易看懂，我主要是通过这个例子，来帮助大家明确dp数组的含义。
上图中，我们看 dp[1][4] 表示什么意思呢。
任取 物品0，物品1 放进容量为4的背包里，最大价值是 dp[1][4]。
通过这个举例，我们来进一步明确dp数组的含义。
即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
2.确定递推公式:
当前背包容量为j放入物品i，这里可以分成两种情况：
背包空间不够放入物品i：取不放物品i时的最大价值dp[i-1][j]；
足够放入物品i:比较不放物品i时的最大价值dp[i-1][j]和放入后的总价值dp[i-1][j-weigh[i]]+value[i];
（可以理解为没放入之前已有的最大价值dp[i-1][j-weigh[i]]加上当前物品的价值）因此这里的递推公式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
具体分析：
首先我们要明确有哪些方向可以推导出 dp[i][j]。
这里我们dp[1][4]的状态来举例：
求取 dp[1][4] 有两种情况：
- 放物品1
- 还是不放物品1
如果不放物品1， 那么背包的价值应该是 dp[0][4] 即 容量为4的背包，只放物品0的情况。
推导方向如图：
如果放物品1， 那么背包要先留出物品1的容量，目前容量是4，物品1 的容量（就是物品1的重量）为3，此时背包剩下容量为1。
容量为1，只考虑放物品0 的最大价值是 dp[0][1]，这个值我们之前就计算过。
所以 放物品1 的情况 = dp[0][1] + 物品1 的价值，推导方向如图：
两种情况，分别是放物品1 和 不放物品1，我们要取最大值（毕竟求的是最大价值）
dp[1][4] = max(dp[0][4], dp[0][1] + 物品1 的价值)
3.dp数组如何初始化：
第一列：表示背包容量为0时放入下标0到i的物品，无意义，因此第一列不用初始化（或者全初始化为0）
第一行：表示背包容量为0到j时放入下标为0的物品，当背包容量大于物品0的重量时，才能放入。因此这里从物品0的重量到背包总重量全都初始化为物品0的价值
4.确定遍历顺序：
在如下图中，可以看出，有两个遍历的维度：物品与背包重量
那么问题来了，先遍历 物品还是先遍历背包重量呢
其实都可以（虽然两个for循环遍历的次序不同，其实根本不影响dp[i][j]公式的推导）， 但是先遍历物品更好理解。（把物品i放入背包容量从0到背包总重所能存入的最大价值）
注意这里物品从1开始遍历，因为物品0已经初始化过了
要理解递归的本质和递推的方向。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。
dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向（包括正上方向），那么先遍历物品，再遍历背包的过程如图所示：
5.举例推导dp数组：
来看一下对应的dp数组的数值，如图：
最终结果就是dp[2][4]。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,bagw;
cin>>n>>bagw;
vector<int>value(n,0) ;
vector<int>weigh(n,0);
for(int i=0;i<n;i++)cin>>weigh[i];
for(int i=0;i<n;i++)cin>>value[i];
vector<vector<int>>dp(n,vector<int>(bagw+1,0));
for(int j=weigh[0];j<=bagw;j++){
dp[0][j]=value[0];
}
for(int i=1;i<n;i++){
for(int j=0;j<=bagw;j++){
if(j-weigh[i]<0)dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weigh[i]]+value[i]);
}
}
cout<< dp[n-1][bagw]<<endl;
return 0;
}01背包问题 一维：
对于背包问题其实状态都是可以压缩的。
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。
动规五部曲:
1.确定dp数组以及下标的含义：
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]
2.确定递推公式：
二维dp数组的递推公式为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
一维把物品下标优化掉了，直接把上一层的拷贝到这一层就好了,
所以在 上面递推公式的基础上，去掉i这个维度就好。
dp[j] = max(dp[j], dp[j] -weight[i]] + value[i])
3.dp数组如何初始化：
关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
dp在推导时一定取的是最大值，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。
因此全部初始化为0
4.确定遍历顺序：
这里和二维有比较大的区别了
首先这里在遍历背包时要从大（背包总重）到小（物品i的重量）以保证物品i只被放入一次
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒序遍历，就可以保证物品只放入一次呢？
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
而对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖
因此这里二维遍历背包时是要从0到背包总重（如果从物品i重量到背包总重的话，遍历下一层/下一个物品时会出现上一层没有数据可以用的情况）
以及物品从下标0开始遍历，因为二维初始化了第一行，而一维创建数组的时候默认为0了，所以这里是没有遍历过物品0的
代码中是先遍历物品嵌套遍历背包容量的，如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
5.举例推导dp数组：
一维dp，分别用物品0，物品1，物品2 来遍历背包，最终得到结果如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,bagw;
cin>>n>>bagw;
vector<int>value(n,0) ;
vector<int>weigh(n,0);
for(int i=0;i<n;i++)cin>>weigh[i];
for(int i=0;i<n;i++)cin>>value[i];
vector<int>dp(bagw+1,0);
for(int i=0;i<n;i++){
for(int j=bagw;j>=weigh[i];j--){
dp[j]=max(dp[j],dp[j-weigh[i]]+value[i]);
}
}
cout<< dp[bagw]<<endl;
return 0;
}416. 分割等和子集
背包问题有多种背包方式，常见的有：01背包、完全背包、多重背包、分组背包和混合背包等等。
要注意题目描述中商品是不是可以重复放入。
即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的。
要明确本题中我们要使用的是01背包，因为元素我们只能用一次。
这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。
只有确定了如下四点，才能把01背包问题套到本题上来。
- 背包的容量为sum / 2
- 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
以上分析完，我们就可以套用01背包，来解决这个问题了。
动规五部曲:
1.确定dp数组以及下标的含义：
dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量（之前这里是价值）为dp[j]。
那么如果背包容量为target， dp[target]就是装满 背包之后的重量（之前这里是价值），所以 当 dp[target] == target 的时候，背包就装满了。（因为本题元素价值就是重量）理解这点很重要
装不满的情况：
拿输入数组 [1, 5, 11, 5]，举例， dp[7] 只能等于 6，因为 只能放进 1 和 5。
而dp[6] 就可以等于6了，放进1 和 5，那么dp[6] == 6，说明背包装满了。
2.确定递推公式：
01背包的递推公式为：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数组如何初始化：
本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了
4.确定遍历顺序：
具体见上题
5.举例推导dp数组：
dp[j]的数值一定是小于等于j的。
如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。
用例1，输入[1,5,11,5] 为例，如图：
最后dp[11] == 11，说明可以将这个数组分割成两个子集，使得两个子集的元素和相等。
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]);
}
}
return dp[target] == target? true:false;
}
};原文地址：https://blog.csdn.net/2403_88990400/article/details/144430373
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！