动态规划 （Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。有言在先：DP和贪心一样，是一种思想，可以指导我们分析题目，但没有具体模板。
T1.[01背包问题]
输入：
第一行输入N 和 M，代表物品数量和背包体积上限
接下来的N行，每行输入两个数字，分别代表物品的体积和价值
输出：
输出一个数字，代表不超过背包体积上限的情况下，所拿物品的最大价值之和
注意：每个物品最多只能拿一次！
不难发现核心代码如下：
if(j<v[i])
{
f[i][j]=f[i-1][j];
}
else if(j>=v[i])
{
f[i][j]=f[i-1][j-v[i]]+w[i];
}#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;//总物件数量和体积上限
int v[N], w[N];//每个物件的体积v和价值w
int f[N][N];//状态
int main()
{
cin >> n >> m;
//因为f[0][0~m]代表前0件物品总体积不超过0~m的最大总价值，所以不需要赋值（全局变量自动赋值为0）
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i=1;i<=n;i++)
for (int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];//图中左子集
if (j >= v[i])f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);//图中右子集
//当前f[i][j]最大值已通过max找到
}
cout << f[n][m] << endl;
return 0;
}DP问题优化：
指对核心代码进行简化，不改变原来的意义
/*优化：将01背包问题的状态方程转化为一维数组*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int f[N];//一维状态方程
int v[N], w[N];//每个物品的体积和价值
int n, m;//n个物品，m为体积上限
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)//第五章-动态规划(三)42分
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}-2022-0929-
经过长时间的视频学习，大概对01背包问题的优化有了一点了解：用到了滚动数组的概念（应该就是只用长度不变的数组（只利用那么几个空间），然后不断地更新某位置上的数值，可以联想到保险箱上的滚动保险锁），那么也就是不断的取i-1层的最大价值f[j]（在前i个物品里面选，但是不选第i个物品；在前i-1个物品里面选，但前提是已经默认选择了第i个物品，所以需要留出v[i]的体积空间，再加上i的价值w[i]）
那么问题就来了！之前是二维数组时，有i可以明显的帮我们分层，保证我们始终对比的是上面括号内的两个部分，现在没有i分层了，就会把f[j]搞混，因为如果还是从j升序的思想去实现，就会造成混乱：我所比较的f[j] = max(f[j], f[j - v[i]] + w[i]); 会在（第i层，也就是当前更新的这一层）从小变大的f[j]更新过程中，丢失本该用来比较的第i-1层的f[j]数据，所以结果就不对了！【yxc：j-v[i]是严格小于j的，所以max第二部分是第i层的，而不是我们想要的第i-1层的，为了修改这种错误，要改变遍历的方向】
这也就是为什么我们在优化二维状态数组为一维状态数组之后，第二层for循环的遍历方向改为了从大到小遍历。因为 j-v[i]是严格小于j的 ，所以每次更新f[j]的时候，不用担心滚动数组的前半部分有所改变，也就是更新滚动数组时，没有影响还未更新的位置 所需要的第i-1个位置的 f[j-v[i]]，至此，优化问题已解决。
T2.[完全背包问题]
完全背包问题相对于 01背包问题 的区别就是完全背包的每个物品都没有数量上限（也就是想拿几个就拿几个）
输入：
第一行输入N 和 M，代表物品数量和背包体积上限
接下来的N行，每行输入两个数字，分别代表物品的体积和价值
输出：
输出一个数字，代表不超过背包体积上限的情况下，所拿物品的最大价值之和
注意：每个物品的数量不限
其实基础的思路大差不差，只是在考虑01背包问题的时候仅需要把当前选法分为两类：取第i个物品和不取第i个物品。而完全背包问题就是将选法分为k+1种情况，就是对于第i个物品：不取，取一个，取两个，...取k个（k*v[i]<=j，即k个i物品的体积之和小于当前要求的体积上限）。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)//从前i个物品中选择
for (int j = 0; j <= m; j++)//总体积不超过j的集合
for (int k = 0; k * v[i] <= j; k++)//第i个物品选择k个的情况 遍历
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + w[i] * k);
cout << f[n][m] << endl;
return 0;
}不难发现这种三层循环是比较浪费时间的，所以找找规律，有了以下优化：
f[i][j] =Max(f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w,... )
f[i]i[j-v]=Max( f[i-1,j-v] , f[i-1.j-2v]+w , f[i-1,j-3v]+2w,... )
由以上规律可以发现：f[i][j]的后半部分（除了max的第一项）的最大值其实就等于f[i][j-v]的最大值，运用这个特点可以大大减少我们的工作量-->将原来寻找所有可能的k值的第三层循环简化为两步，即--> f[i,j]=Max(f[i-1,j],f[i-1,j]+w)
所以我们的代码可以优化为：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i=1;i<=n;i++)
for (int j = 0; j <= m; j++)
{
//通过找到f[i][j]和f[i][j-v[i]]之间的关系，得到下面的优化公式（下下行）
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}（两层循环还是比三层循环看着舒服多了lol）
但是，这还不是我们可以优化所得到的终极代码！
可以发现，完全背包问题和01背包问题所依赖的数组是不一样的，完全背包问题的状态方程就是要利用当前的i，而不是i-1，所以在第二层循环时不需要将顺序反过来。【此处有点困惑】
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= m; j++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}T3.[多重背包问题]
多重背包问题和01背包问题的区别在于物品的数量是有限个s[i],可以任取。
输入：
第一行输入两个数字N和M，代表物品种数和背包体积上限；
接下来的N行，每行输入三个数字，分别代表该物品的体积、价值和数量上限
输出：
输出最优解（合规的价值最大值）
题目保证N和M的值不大于100；
如果只是朴素算法，可以思考发现数据范围较小的多重背包问题其实也是可以通过三重循环写出来的，比如 N和M的值不大于100，三重循环后的数据大小最坏为百万级，是可以接受的。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k * v[i] <= j && k <= s[i]; k++)
{
f[i][j] = max(f[i][j], f[i - 1][j - v[i]*k] + w[i]*k);
}
cout << f[n][m] << endl;
return 0;
}我们之前要控制物品拿取的数量乘上体积不大于当前要求的体积，现在也是同理，只要加上k关于s[i]的限制即可。
但是这种朴素、暴力的写法遇到稍微大一点的数量级就会失效，比如说将N和M的数量范围调到1000，那么三重循环需要处理的数据大小最坏为十亿级，明显超过了C++的每秒运算标准（yxc：1e9/s）。如果非要尝试的话，最后的结果会是RE/TLE。
为了想出更好的解法，能不能想完全背包问题那样找到f[i][j]和f[i][j-v]之间的关系呢？可以找到，但是发现无法像完全背包那样应用。↓
f[i,j] = max(f[i-1,j], f[i-1,j-v]+w, f[i-1,j-2v]+2w, ... ,f[i-1,j-sv]+ sw );
f[i,j-v]= max( f[i-1,j-v], f[i-1,j-2v]+ w ,... f[i-1,j-sv]+(s-1)w, f[i-1,j-(s+1)w]+sw);
可以发现在尾部，f[i,j-v]会多出来一部分，而max函数没有什么操作能够忽略最后这一步。于是我们需要一个新的优化方法：二进制的优化方式 。
（具体怎么解释二进制优化方式我不好详细的解释，就是1+2+4+8+16+...+2^k,确保2^k+1能够不超过我们要求的个数）
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 25000, M = 2010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
//二进制优化法
int cnt = 0;
for (int i = 1; i <= n; i++)
{
int a, b, s;
cin >> a >> b >> s;
int k = 1;
while (k <= s)
{
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0)
{
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}这样写就可以面对如N、M、v、w、s等值增加到以千为单位的计算量了。
T4.[分组背包问题]
分组背包问题在考虑状态计算时，所分成的集合是这样的：取第i组第k个物品。
//输入：第一行输入N和M，代表组数和背包体积上限
// 接下来，输入s[i]，代表第i组的物品个数，然后换行输入s[i]个物品的v、w
//输出：求出最优解
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int f[N];
int v[N][N], w[N][N], s[N];
int n, m;
int main()
{
cin >> n >> m; //n组物品，背包体积上限为m
for (int i = 1; i <= n; i++)
{
cin >> s[i];
for (int j = 0; j <= s[i]; j++)
cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= n; i++)//组数限制
for (int j = m; j >= 0; j--)//每组的物品种类限制
for (int k = 0; k < s[i]; k++)//每种物品的拿取数量限制
if (v[i][k] <= j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[m] << endl;
return 0;
}分组背包问题在采用一维数组（滚动数组）来优化时，也是利用上一层i来不断更新，所以需要我们在第二层循环将j的变化方向改为从大到小变化。这也是区分完全背包优化方式和其他背包优化方式的重点。
注意：第一层对于i的循环，限制条件时组数，而不是物品总数！！