今天是动态规划的另一个大类，背包问题。
背包问题的分类
这张图中涵盖了我们能遇到的绝大部分背包问题。
首先是01背包问题
01背包问题
01背包问题：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
对于01背包问题的解法，从dp数组的定义来看，可以写成二维数组和一维数组，接下来使用五部曲来分析分析这两种的写法区别。
这里先放一个例子，分析也都是通过这个例子来进行的：
背包最大重量为4。
物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
问背包能背的物品最大价值是多少？
二维dp数组
1.dp数组的含义
因为背包问题涉及背包容量与物品两个维度，所以可以使用二维数组。那么对于dp[i][j]来说，这里假设i表示物品编号，j表示物品容量。
那么对于dp数组的含义呢？
从图中可以看出来，dp数组的含义
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
2.递推公式
dp[i][j]是由那些位置所决定的呢？
假设对于dp[1][4],表示在0到1之间的物品任取放入背包容量4的背包中所能得到的最大价值。
求取 dp[1][4] 有两种情况：
- 放物品1
- 还是不放物品1
假设不放物品1，那么这个值应该是物品0放入背包4的最大价值，是15。
假设放入物品1，那么在放入物品1 之前需要确保背包的容量足够，那么才能放入物品1，并且需要价值最大，那么就需要保证出去物品1的容量后，背包的价值应改保持最大，此时表示为dp[i-1][j-weigth[i]]。那么再加上物品1的价值，就是放物品1的最大价值。
综上来看：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weig]th[i]+value[i])
3.初始化
根据之前的分析，就能很清楚的看出来如何初始化。而其他的部分，按照dp的递推公式来看，初始化为什么其实都不重要，因为都会被覆盖掉。
4.遍历顺序
两个维度，物品与背包容量，其实先遍历谁都一样，结合dp公式和图来看，每一个dp都是有上一层和左上角位置所决定的，那么无论先遍历谁，这两个值都会提前被确定下来，所以不会影响dp[i][j]的值。
题目：携带研究材料（第六期模拟笔试）
46. 携带研究材料（第六期模拟笔试） (kamacoder.com)
题目描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。
小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。
输入描述
第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。
第二行包含 M 个正整数，代表每种研究材料的所占空间。
第三行包含 M 个正整数，代表每种研究材料的价值。
输出描述
输出一个整数，代表小明能够携带的研究材料的最大价值。
题目分析：
标准的01背包问题。看代码
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
int n, bagweight;// 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];
}
//dp数组定于
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
// 初始化, 因为需要用到dp[i - 1]的值
// j < weight[0]已在上方被初始化为0
// j >= weight[0]的值就初始化为value[0]
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
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]; // 如果装不下这个物品,那么就继承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;
}一维dp数组(滚动数组)
在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把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]（一维数组，也可以理解是一个滚动数组）。
那么继续五部曲：
dp数组的含义，和二维数组的差不多
在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
递推公式
因为是将上一层的复制过来，所以不用考虑i的问题
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
因为是复制过来的，dp[j]这个位置本身是有值的，所以需要和自身比较。
初始化
dp[0]的位置很明显是0，那么其他位置呢？考虑到递推公式中需要和自身进行比较，为了不影响这个过程，初始化为0即可。
遍历顺序
这里先给出遍历的代码
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[j]时，将dp[j]的上一层提前复制，而在这一层会依靠上一次的结果，导致物品被多次放入。所以倒序遍历是为了保证物品i只被放入一次！
那么他们之间的顺序是否可以像二维dp那样颠倒呢？
不可以。因为他是依赖于上一层的。
同样的题目，使用一维数组求解。
题目：携带研究材料（第六期模拟笔试）
46. 携带研究材料（第六期模拟笔试） (kamacoder.com)
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
// 读取 M 和 N
int M, N;
cin >> M >> N;
vector<int> costs(M);
vector<int> values(M);
for (int i = 0; i < M; i++) {
cin >> costs[i];
}
for (int j = 0; j < M; j++) {
cin >> values[j];
}
// 创建一个动态规划数组dp，初始值为0
vector<int> dp(N + 1, 0);
for(int i=0;i<M;i++){
for(int j=N;j>=costs[i];j--){
dp[j]=max(dp[j],dp[j-costs[i]]+values[i]);
}
}
// 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值
cout << dp[N] << endl;
return 0;
}好了，看完01背包的基础，来看一看他的应用题
题目：分割等和子集
416. 分割等和子集 - 力扣（LeetCode）
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
题目分析：
首先，本题要求集合里能否出现总和为 sum / 2 的子集。
那么来一一对应一下本题，看看背包问题如何来解决。
只有确定了如下四点，才能把01背包问题套到本题上来。
- 背包的体积为sum / 2
- 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
那么按照五部曲开始走。
dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。那么如果背包容量为target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了。
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]);
public class Solution {
public bool CanPartition(int[] nums) {
int sum=0;//数组和
for(int i=0;i<nums.Length;i++){
sum+=nums[i];
}
if (sum % 2 == 1) return false;
int target = sum / 2;
int[] dp = new int[10001];//拆成2半,所有取和的一半即可
for(int i=0;i<nums.Length;i++){
for(int j=target;j>=nums[i];j--){
dp[j]=Math.Max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
if (dp[target] == target)
return true;
return false;
}
}对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。
代码随想录 (programmercarl.com)