代码随想录-训练营-day30

今天我们要进入动态规划的背包问题，背包问题也是一类经典问题了。总的来说可以分为：

今天让我们先来复习0-1背包的题目，这也是所有背包问题的基础。所谓的0-1背包问题一般来说就是给一个背包带有最大容量，然后给一个物体对应的需要的容量和价格的表格，且每个物体只能取一次，问我们怎么得到最大价值。

我们依然使用动态规划的既定套路来做：

第一步，确定我们的dp数组的含义，首先明确的是：我们需要一个二维的dp数组，因为我们需要同时表示背包的容量和物体，也就是dp[i][j]表示的是容量为j的背包中遍历到下标为i的物体时的最大价值。

第二步，递推公式，我们可以设想一下dp[i][j]可以怎么由之前的值得到，对于容量为j的背包来说，物体i有两种情况：放或者不放，不放的话就是dp[i-1][j],放的话就是dp[i-1][j-weights[i]]+values[i]（要放下标为i的物体需要在背包中预留出他的容量），所以递推公式就是：

dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i]]+values[i])

第三步，初始化，我们要如何初始化我们的dp数组呢？显然dp[0][0]=0(容量为0)，事实上，所有容量为0的背包的初始值都应该是0，也就是dp[i][0]=0;那么反过来的dp[0][j]呢？这个就要看我们下标为0的物品重量与我们的j的关系了，如果大于j显然也是0，如果小于j的话那就可以是values[0]。那么dp[0][j]应该就是从j=weights[0]开始，遍历到最后。

最后的初始化结果如下：

遍历顺序的话，也很有讲究，我们是该先遍历物品呢，还是该先遍历背包呢？

答案其实是，对于0-1背包来说，都可以。

我们拿一个图来说明：

由我们的递推公式已知，我们的dp[i][j]的更新都是依靠左上角的值来更新的，那么我们先遍历背包再遍历物品就是先横向再纵向，反之是先纵向再横向，但最后我们都是往右下角推进的，都是符合要求的，所以对于这个题来说，先遍历哪个都是可取的。

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

是的小明是一位科学家但是不重要，因为这就是一个标准的动态规划的背包问题，让我们开始做吧。

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

这个题需要注意的一点是：我们讨论物品的时候是根据下标来的，是从0开始的，也就是物品有n种，但是我们遍历只遍历到n-1；而容量是从1开始的，也就是我们得从1遍历到具体的容量值，而同样的我们返回的也得是dp[n-1][zooms]才可。

虽然我们的分析已经完成，但是并非没有可以改善之处。比如我们其实不难发现我们的现在的遍历的j都是从0开始，去判断当前j和weights[i]的关系。但实际上，我们还有更聪明的做法：

dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i]]+values[i])这是我们的递推公式，但是我们可以注意到的是，dp[i-1][j]就是位于dp[i][j]的正上方，也就是说其实我们更多地只是在看我们的另一项，否则我们会直接继承dp[i-1][j]，那么这个时候我们就可以选择不用i来记录每一个这个数，而是将i这个维度去掉来不断更新我们的dp[j]达到相同的效果：

这样我们的递推公式就变成了：dp[j]=max(dp[j],dp[j-weights[i]]-values[i])。可以看到我们的数组一下就变成了一个一维数组，这样无疑大大减小我们的空间复杂度，也更清晰明了。

让我们再重复一遍我们的动态规划的步骤：

首先确定dp数组的含义，对于一维数组dp[j]来说，显然dp[j]代表背包容量为j时能填充的最大价值。

递推公式，已知是dp[j]=max(dp[j],dp[j-weights[i]]-values[i])。

然后是初始化，对于dp[0]来说，显然等于0。

遍历顺序，这个是背包问题中最值得讲究的点：我们一般来说都是循环的顺序都是先遍历物品再遍历背包容量，这个在一维数组的情况也适用。然后是我们关于物品和背包的遍历方式，物品我们依然还是从下标为0开始遍历到n-1，但是我们的背包容量遍历就必须要反过来，也就是：

for(int j=zooms;j>=weights[i];--j)为什么呢？因为我们的dp[j]是完全由dp[j]与dp[j-weights[i]]+values[i]来递推的，对于i来说并没有专门记录，如果从0开始遍历到zooms，我们很可能会反复添加一个物品（比如背包容量为2，可以装两次重量为1的物体），导致违背了0-1背包的一个物体只能使用一次的原则。而反着来遍历的话，我们其实是从大往小遍历，只要题目设计合理，我们就可以避免这个问题。

让我们再用一维数组的方式做一遍携带研究材料吧：

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

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

这个题乍一看可能还挺难想到是用动态规划来做，但是随着我们的思路慢慢一路顺延其实很自然地就能想到。

首先我们要求将数组分割成两个元素和相等的子集，那么我们的第一层尝试自然是求数组的总和后整除2，如果都不能整除成功就可以直接返回false。然后就是我们需要尝试将数组的一个个元素塞进一个数组中，要求这个数组的和为我们大数组的总和的一半。是不是有一种既视感？是的，其实我们的容量就是这个总和的一半，大数组里的数字就是我们的value。

class Solution {
public:bool canPartition(vector<int>& nums) {int sum=accumulate(nums.begin(), nums.end(), 0);if(sum%2!=0)return false;int target=sum/2;vector<int> dp(target+1,0);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;}
};

第一步：dp数组的含义：dp[i]代表容量为i的背包中能包含的最大和。

第二步：递推公式：dp[i]=max(dp[i],dp[i-nums[i]]+nums[i])，这里我们的物体的重量和价值是一样的。但是重量是重量，价值是价值，概念上不可以混淆。

第三步，初始化，全部初始化为0即可。

第四步，确定递推顺序，这个我们在之前的一维数组部分已经讲解了。