一、背包问题简述以及01背包解题思路
背包问题包括01背包、完全背包、多重背包等。其中基础和重点就是01背包和完全背包，所以我们现在就背包问题中的01背包和完全背包问题进行学习，使用动态规划解决背包问题。
01背包是其他背包的基础，我们首先对01背包进行学习。纯粹的01背包问题一般描述如下：有n种物品，每种物品只有一个，每个物品有自己的重量和价值，有一个最多只能放重量为m的背包，求这个背包最多能装价值为多少的物品。
我们选择二维dp数组实现。首先我们需要知道动态规划数组的含义。dp[i][j]表示[0,i]物品放入容量为j的背包中的最大价值。dp[i][j]的值的推导我们可以讨论放不放物品i，如果不放物品i则值为dp[i-1][j]；如果放，则为dp[i-1][j-weight[i]]+value[i]。所以递推公式为dp[i][j] = max(dp[i-1][j-weight[i]]+value[i], dp[i-1][j])。
然后找初始化什么。我们由递推公式可以知道，dp[i][j]是由dp数组左上角的值得到的，所以我们可以对第一行和第一列进行初始化为应有的值。
接着确定遍历顺序。根据推导，我们从左到右从上到下遍历即可，无论是for循环先遍历背包还是先遍历物品，都可以。
二、代码练习：携带研究材料
选取了卡码网的一道题46. 携带研究材料（第六期模拟笔试） (kamacoder.com)，非常标准的经典的01背包问题。采取上面讲述的思路编写代码，即可得到如下完整代码：
#include <bits/stdc++.h>
using namespace std;
int n, bag;
void solve()
{
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];
}
vector<vector<int>> dp(weight.size(), vector<int>(bag + 1, 0));
for (int j = weight[0]; j <= bag; j++)
{
dp[0][j] = value[0];
}
for(int i = 1; i < n; i++)
{
for(int j = 0; j <= bag; 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]);
}
}
cout << dp[n - 1][bag] << endl;
}
int main() {
while(cin >> n >> bag) {
solve();
}
return 0;
}三、代码练习：分割等和子集
题目为416. 分割等和子集 - 力扣（LeetCode），给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
要注意题目描述中商品是不是可以重复放入。商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，本题为01背包。
本题如何视作01背包呢，我们把sum/2视为背包体积，商品重量和价值均为元素数值。如果背包能正好装满，则为可分割等和子集。
然后我们使用动规五部曲：
①确定dp数组含义。本题我们尝试使用一维dp数组。dp[j]含义为背包容量为j时，放进物品的最大重量。如果dp[j]==j则说明装满了。
②递推公式。dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
③初始化。dp[0]初始化为0。
④遍历顺序。因为本题使用的为一维dp数组，所以需要物品循环的for放在外层，遍历背包的for放在内层且内层循环倒序遍历。倒序遍历才能保证每个物品只添加一次（这里比较绕，可以举例子思考一下，我的理解为：因为外面循环是遍历物品，里面是遍历容量，也就是说对于不同容量是否加入这个物品观察结果，然后因为递推公式需要用到前面的结果，如果从前往后遍历则前面已经考虑过是否放改物品了后面还要放，则会导致多次放，如果从后往前，此时前面还未考虑过是否放该物品，所以不影响）。
⑤推导/打印dp数组进行观察和检查。
完整代码如下：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i = 0; i < nums.size(); i++)
{
sum += nums[i];
}
vector<int> dp(sum/2+1,0);
if(sum%2 == 1) return 0;
for(int i = 0; i<nums.size(); i++)
{
for(int j = sum/2; j>=nums[i]; j--)
{
dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
return dp[sum/2]==sum/2;
}
};说明：本文为作者整理知识点用于复习巩固，参考了代码随想录的讲解，有问题可以联系作者欢迎讨论~
