代码训练营 day39|0-1背包问题，LeetCode 416

前言

这里记录一下陈菜菜的刷题记录，主要应对25秋招、春招
个人背景
211CS本+CUHK计算机相关硕，一年车企软件开发经验
代码能力：有待提高
常用语言：C++

系列文章目录

第九章 动态规划part03

---

`

---

---

一、今日任务

● 01背包问题 二维
● 01背包问题 一维
● 416. 分割等和子集

二、详细布置

背包问题详解

完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的

二维数组版本

dp数组定义

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

dp递推公式

-不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。
-放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

dp数组初始化

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
在看其他情况。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出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物品。

for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}

最后初始化代码如下：

// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}

确定遍历顺序

先遍历物品更好理解

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); 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]);}
}

一维数组版本

确定dp数组的定义

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

一维dp数组的递推公式

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

一维dp数组遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

注意:这里和二维dp的写法中，遍历背包的顺序是不一样的！

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
倒序遍历是为了保证物品i只被放入一次！
代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？

不可以！

初始化

dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

46. 携带研究材料

题目链接：卡码网46
文章讲解：代码随想录

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入：
第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。

第三行包含 M 个正整数，代表每种研究材料的价值。

输出：
输出一个整数，代表小明能够携带的研究材料的最大价值

提示：

数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000

样例1：

输入：
1 6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出：
5
解释：
小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。 

思路

这题就是0-1背包问题的经典应用。

实战

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

一维数组求解法

#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);int i,j;for(i=0;i<n;i++)cin>>weight[i];for(j=0;j<n;j++)cin>>value[j];vector<int> dp(bagweight+1,0);for(i=0;i<n;i++){for(j=bagweight;j>=weight[i];j--){dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);}}cout<<dp[bagweight]<<endl;return 0;
}

416. 分割等和子集

题目链接：LeetCode426
文章讲解：图文讲解

题目描述

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

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

样例1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 

样例2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

思路

0-1背包的变形。

实战

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

总结

今天主要学习了0-1背包问题，老师讲的很详细，理解起来不难。后面还需要多做题巩固一下代码。
加油，坚持打卡的第39天。