01背包问题理论
背包问题分类图：
其中01背包问题是基础，问题描述为：有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
当然可用类似组合思想回溯暴力，但是复杂度太高，使用动态规划解决。
动态规划五部曲：
1.确定dp数组以及下标的含义
首先是二维dp数组，dp数组的维度由动态规划中可变状态决定。
本题有两个维度需要分别表示：物品 和 背包容量
如图，二维数组为 dp[i][j]，其中i 来表示物品、j表示背包容量、dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
2.确定递推公式
针对d[i][j]，也就是判断到物品为i，背包容量为j的问题了，它的状态与之前什么有关呢（之前显然为0 — i-1物品，背包容量为0 — j-1）？
对于第i个物品，如果容量大于j，肯定放不进去，dp[i][j] = dp[i-1][j]。
推导方向如图：
对于第i个物品，如果容量小于等于j，需要放进去比较试试dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]
推导方向如图：
3.dp数组如何初始化
关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
dp[i][j]是由上方、左上方推导而来，并且存在i-1、j-weight[i]等可能越界行为，需要进行完善.
- 存在
i-1，则一开始需要从i = 1遍历，并且把第0行初始化 - 存在
j-weight[i]，需要判断j>=weight[i]才可进行后续 dp[i][j]是由上方、左上方推导而来，故初始化第一行即可，剩下的不用管。
4.确定遍历顺序
在如下图中，可以看出，有两个遍历的维度：物品与背包重量:
那么问题来了，先遍历 物品还是先遍历背包重量呢？
其实都可以！！ 但是先遍历物品更好理解。
因为根据递推的本质，dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。
5.举例推导dp数组
dp数组优化
由上文可知，当前状态dp[i][j]与上方与左上方有关，仅仅是上一行（创建所有状态的储存空间较为浪费），所以可压缩二维数组变为一维数组。
时刻谨记二维dp数组的含义，压缩为一维dp[j]后,其含义为：背包容量为j，容纳的最大价值是多少。
递推公式为：dp[j] = max(dp[j],dp[j-weight[i]]+value[i])，每个仅与左侧有关，故可从物品0逐行遍历
遍历顺序： 当前状态仅与左侧相关，故需要从右向左遍历，很重要！
46.携带研究材料
思路
01背包问题，根据理论基础即可解答
题解
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int m = 0,x = 0,n = 0;
cin>>m>>n;
vector<int> weight;
vector<int> value;
for(int i = 0;i<m;i++)
{
cin>>x;
weight.push_back(x);
}
for(int i = 0;i<m;i++)
{
cin>>x;
value.push_back(x);
}
// 二维dp数组
// vector<vector<int>> dp(m,vector<int>(n+1,0));
// for(int j = 0;j<=n;j++)
// {
// if(j>=weight[0])dp[0][j] = value[0];
// else dp[0][j] = 0;
// }
// for(int i = 1;i<m;i++)
// {
// for(int j = 0;j<=n;j++)
// {
// if(j>=weight[i])
// {
// dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
// }
// else dp[i][j] = dp[i-1][j];
// }
// }
// cout<<dp[m-1][n]<<endl;
//一维dp数组
vector<int> dp(n+1,0);
for(int i = 0;i<m;i++)
{
for(int j = n;j>=0;j--)
{
if(j>=weight[i])dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
}
}
cout<<dp[n]<<endl;
return 0;
}
416.分割等和子集
题目链接：416.分割等和子集
文档讲解：代码随想录
状态：不会，不知道怎么转化背包问题
思路
问题转化：能否找出数组中加和为sum/2的组合？
貌似是很典型的回溯问题，回溯是一般是找出所有数据、种类、组合等，而本题仅仅要求一个bool值
转化为背包过程的关键点：当容量定义为价值时，dp[j] == j是情况存在的充要条件。
题解
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(auto &i:nums)sum+=i;
if(sum%2!=0)return false;
sum /= 2;
vector<int> dp(sum+1,0);
for(int i = 0;i<nums.size();i++)
{
for(int j = sum;j>=nums[i];j--)
{
dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
if(dp[sum] == sum)return true;
else return false;
}
};