前言
唤我沈七就好啦。
动态规划
核心作用：优化
当数据范围> 30 时 单纯用暴力（DFS BFS）的话指数型枚举必然超时
而动态规划能以某种比较聪明的方式来枚举所有方案。
最后按题目要求（属性）求解。
dp、递归、递推、搜索 的关系
dp 是递推，是搜索的改版，是递归的进化体.
初始化
DP 的细节包括你说的初始化问题，是没有很固定的模板的，一般情况下可以归纳以下三种情形：
求最大值，将所有值初始化为无穷小，找到 DP 的起点（边界），手动赋值；
求最小值，将所有值初始化为无穷大，找到 DP 的起点（边界），手动赋值；
求方案数，将所有值初始化为 0 ，找到 DP 的起点（边界），手动赋值，一般为 1 。
在还没有熟悉的时候，建议认真找到所有边界值，并给它们赋上初值，这样的方式肯定是正确的。
熟悉了以后，针对某些特定的题目，可以根据经验，遵循 不影响最终答案 的原则，省略部分赋值的步骤。
状态转移方程涉及到 i-1 从 i 就从1开始循环，没涉及就从 0 开始。
01背包
二维背包
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 v[i]，价值是 w[i]
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
dp[i] [j] 含义：前 i 个物品，背包容量 j下的最优解（最大价值）：
（1）当前的状态依赖于之前的状态，可以理解为从初始状态dp[0] [0] = 0 开始决策，
有 N 件物品，则需要 N 次决 策，每一次对第 i 件物品的决策， 状态f[i] [j]不断由之前的状态更新而来。
（2）当前背包容量不够（j < v[i]）
没得选，因此前 i个物品最优解即为前 i−1个物品最优解：
对应代码：f[i][j] = f[i - 1][j]。
（3）当前背包容量够，可以选，因此需要决策选与不选第 i个物品：
选： f[i][j] = f[i - 1][j - v[i]] + w[i]。 不选：f[i][j] = f[i - 1][j] 。 我们的决策是如何取到最大价值，因此以上两种情况取 max() 我们的决策是如何取到最大价值，因此以上两种情况取 max()
为什么选的状态转移 方程 是 f[i] [j] = f[i - 1] [j - v[i]] + w[i] 呢
下面我来说一下我的理解
d p [i-1] [j-v[i]]+w[i ] 代表着 “必选第i个物品” ，怎么样才能做到“必选”呢 ？
其实只要在一开始的时候将第 i 个物品直接放入背包即可 即 +w[i]
然后只在前 i-1 个物品里选剩下的就行了。
#include<bits/stdc++.h> using namespace std; const int N=1e4; int dp[N][N];// dp[i][j], j体积下前i个物品的最大价值 int v[N],w[N]; int main() { int n,m; 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 = 1 ; j <= m ; j ++) { dp[i][j]=dp[i-1][j]; if(j>=v[i])//j<v[i] dp[i-1][j-v[i]]下标就小于0了 dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]); } cout<<dp[n][m]; return 0; }
一维优化
因为 dp[i] 仅用到了dp[i-1]层, 那我们只需要短暂的存一下上一层，就可以去掉这层了
（ 1 ）dp[j]定义：N件物品，背包容量j下的最优解。
（ 2 ）注意枚举背包容量j必须从m逆序开始。
（ 3 ）为什么一维情况下枚举背包容量需要逆序？
在二维情况下，状态f【i】【j】是由上一轮i - 1的状态得来的，f[i] [j]与f[i - 1] [j]是独立的。
而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。
例如：由于j是从大到小循环的。假设j = 5； j >= 2; j -–;
也就是这一层（第i层）会先算出来f[5],
注意这个时候，第i层正在算f[5], 也就是说第i层没有更新f[4] f[3]，也就是此时的f[4] f[3] 是i - 1层的）
那么算 f[5] 要用到比他更小的 f[4] 或者f[3]也就是i - 1层的了。
（4）简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。
#include<bits/stdc++.h> using namespace std; const int N=1e4; int dp[N]; int v[N],w[N]; int main() { int n,m; 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 = m ; j >= v[i] ; j --) { dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } cout<<dp[m]; return 0; }
经典习题
小A点菜
uim由于买了一些书，口袋里只剩M元(M≤10000)
餐馆虽低端，但是菜品种类不少，有N种(N≤100)，
第i种卖a元(ai≤1000) 由于是很低端的餐馆，所以每种菜只有一份。
小A奉行“不把钱吃光不罢休”，所以他点单一定刚好把uim身上所有钱花完。
他想知道有多少种点菜方法。
dp[ j ] 表示达到当前钱数时，已经求出的方案数；
每一种菜都可以选择吃和不吃
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; int dp[N]; int w[N]; int main() { int n,m; cin>>n>>m; for (int i = 1 ; i <= n ; i ++) cin>>w[i]; dp[0]=1;//因为当钱数==0时，说明当前方案已经成立，所以方案总数加 1 for (int i = 1 ; i <= n ; i ++) for (int j = m ; j >= w[i] ; j --) { dp[j]=dp[j]+dp[j-w[i]]; //可以选吃喝和不吃 } cout<<dp[m]; return 0; }
5 倍经验日
现在 A 拿出了 x个迷药，准备开始与那些人打了。
由于迷药每个只能用一次，所以 A要谨慎的使用这些药。悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。例如他用 2 个药去打别人，别人却表明 3个药才能打过，那么相当于你输了并且这两个属性药浪费了。
现在有 n 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。
要求求出最大经验 s，输出 5 * s 。
题解部分：
dp[i]表示用i瓶药获得的最多经验。
1.如果 j 个迷药打不过，只能加 失败的经验： dp[j]=dp[j]+w1[i]
2.如果打的过 ，可以选择打败他获得获胜经验，也可以选择不打败他获得失败经验
然后就是 0 1 背包思想： dp[j]=max(dp[j]+w1[i],dp[j-v[i]]+w2[i]);
注意 如果要打败他的话，需要消耗 迷药 ，所以需要 j - v[i]
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; long long dp[N],n,m; long long w1[N],w2[N],v[N]; int main() { cin>>n>>m; for(int i = 1 ; i <= n ;i ++) cin>>w1[i]>>w2[i]>>v[i]; for(int i = 1 ; i <= n ; i ++) { for(int j = m ; j >= 0 ; j --) { if(v[i]>j)//如果 j 个迷药打不过，只能加 失败的经验 dp[j]+=w1[i]; else dp[j]=max(dp[j]+w1[i],dp[j-v[i]]+w2[i]); //如果打的过 ，可以选择打败他获得获胜经验，也可以选择不打败他获得失败经验。 //这样问题就转化成了 0 1 背包问题 选和不选 } } cout<<5*dp[m]; return 0; }
买干草
约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草． 顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，
他最多可以运回多少体积的干草呢？
虽然问的是体积，但可以将这个问题看成价值和体积相等
这样就和背包问题 一 模 一 样 了！
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; long long dp[N]; int v[N]; int main() { int m,n; cin>>m>>n; for(int i = 1; i <= n ; i ++) cin>>v[i]; for(int i = 1; i <= n ; i ++) for(int j = m; j >= v[i] ; j --) { dp[j]=max(dp[j],dp[j-v[i]]+v[i]); } cout<<dp[m]; return 0; }
完结散花
ok以上就是对 动态规划之01背包 的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。
参考文献
https://www.acwing.com/activity/content/19/
