关于DP
动态规划（简称DP）是一类思想，主要通过分段求解的方式来解决一些决策类问题。
DP所能解决的问题
能用DP解决的问题需要满足三个条件：
- 最优子结构
- 子问题重叠
- 无后效性
最优子结构
- 证明问题最优解的第一个组成部分是做出一个选择；
- 对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
- 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
- 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。
子问题重叠
我们可以使用记忆化的方法去记录每一个子问题的解，避免重复解答某一个（或多个）子问题，进而降低整个算法的时间复杂度。
无后效性
你当前一步所做的决策不会对后面造成影响（打个比方，数字三角形，你不能走了这一步，你右边的数全都垮了）。
DP的三个要点：
- 状态
- 状态转移方程
- 边界值与求解顺序
背包DP
部分背包
这个好像不是DP吧
给出物品的重量 \(w_i\) 和价值 \(v_i\)，每个物品可以被分割，分割后的性价比不变，问最大价值。
这什么水题啊这题太简单了，直接一个 \(sort\) 然后贪心就完事了。
代码就不写了，懒得写了太简单了。
下一个·
0-1背包
给出物品的重量 \(w_i\) 和价值 \(v_i\)，每个物品只能选一次，问最大价值。
我们设 \(dp_{i,j}\) 为只考虑前 \(i\) 个物品，且容量为 \(j\) 时的最优解。
每一种物品有选与不选两种状态。如果选，那么不难想到 \(dp_{i,j}=dp_{i-1,j-w_i}+v_i\)，因为之前是没考虑这个物品的，所以是 \(i-1\)；\(j\) 代表的是容量，所以是 \(j-w_i\)。
那么如果不放，总容量不会减少，价值也不会增多，所以当选择不放时，\(dp_{i,j}=dp_{i-1,j}\)。
综合一下，就有 \(dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-w_i}+v_i)\)。
for(int i=1;i<=n;i++){//枚举所有物品数量
for(int j=1;j<=c;j--){//枚举所有容量的情况
dp[i][j]=dp[i-1][j];
if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
注意循环顺序即可。
完全背包
给出物品的重量 \(w_i\) 和价值 \(v_i\)，每个物品可以选无数次，问最大价值。
还是一样，我们设 \(dp_{i,j}\) 为只考虑前 \(i\) 个物品，且容量为 \(j\) 时的最优解。
只是在完全背包问题中，每个物品都可以被选无数次。
所以我们可以在内层再套一层循环 \(k\)，用来枚举选择物品的数量。
当然，\(k\) 不可以超过 \(\lfloor \dfrac{w_i}{j} \rfloor\)。否则会数组越界。
因为有 \(k\) 个物品，所以我们的状态转移方程就变成了 \(dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-w_i \times k}+v_i \times k)\)
代码如下：
for(int i=1;i<=n;i++){//枚举所有物品数量
for(int j=0;j<=w[i];j++){//枚举所有容量的情况
for(int k=0;k<=w[i]/j;k++){//枚举所有物品数量的情况
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]*k]+v[i]*k);
}
}
}
如果能熟记 01 背包的话，相信完全背包也没问题。
多重背包
给出物品的重量 \(w_i\) 、价值 \(v_i\) 以及可以选择的次数 \(m_i\)（即每个物品最多选 \(m_i\) 次），问最大价值。
在这里，我们很容易想到将最内层的 \(k\) 循环的条件改一下，于是就有：
for(int i=1;i<=n;i++){//枚举所有物品数量
for(int j=0;j<=c;j++){//枚举所有容量的情况
for(int k=0;k<=m[i];k++){//枚举所有物品数量的情况
if(j>=w[i]*k) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]*k]+v[i]*k);
}
}
}
注意，在改了内层循环之后要加一个 \(\mathsf{if}\)，防止数组越界。
这里同样可以使用滚动数组进行优化。
代码就不展示了。
混合背包
给出物品的重量 \(w_i\) 和价值 \(v_i\) ，然后告诉你哪些是可以选无数次，哪些只能被选 \(m_i\) 次，问最大价值。
这种问题乍一看很吓人，实际上只要用 \(\mathsf{if}\) 判断一下，然后直接套公式。
这里给出伪代码。
for(枚举考虑前 i 个物品){
if(是01背包){
套用01背包状态转移方程;
}
if(是完全背包){
套用完全背包状态转移方程;
}
if(是多重背包){
套用多重背包状态转移方程;
}
}
分组背包
题面通天之分组背包
先翻到上面复习一下01背包
这一题就是在01背包的基础上增加了一个求组数。
我们只需要对于每一组都跑一次01背包就好了。
核心代码如下：
for(int i=1;i<=n;i++)//枚举小组
for(int j=c;j>=1;j--)//枚举容量
for(int z=0;z<k[i];z++)//枚举物品
if(w[i][z]<=j)
dp[j]=max(dp[j],dp[j-w[i][z]]+v[i][z]);
背包问题的滚动数组优化
这里以 01 背包的优化为例。
注意到我们求出一个 \(dp_{i,j}\) 只需要用到上一行比它靠前位置的信息。
于是我们便可以倒着循环，循环中 \(\ge j\) 为本行信息，\(<j\) 为上一行信息，这样可以保证答案一定从上一行转移来。
for(int i=1;i<=n;i++){
for(int j=c;j>=w[i];j++){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}