动态规划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] 为例，如图：

416.分割等和子集2

最后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;}
};