算法模板：动态规划之01背包

• 前言
• 动态规划
• 01背包
• • 二维背包
  • 一维优化
  • 经典习题
  • • 小A点菜
    • 5 倍经验日
    • 买干草
• 完结散花
• 参考文献

前言

唤我沈七就好啦。

动态规划

核心作用：优化

当数据范围> 30 时 单纯用暴力（DFS BFS）的话指数型枚举必然超时
而动态规划能以某种比较聪明的方式来枚举所有方案。
最后按题目要求（属性）求解。

dp、递归、递推、搜索 的关系

dp 是递推，是搜索的改版，是递归的进化体.

初始化

DP 的细节包括你说的初始化问题，是没有很固定的模板的，一般情况下可以归纳以下三种情形：

1. 求最大值，将所有值初始化为无穷小，找到 DP 的起点（边界），手动赋值；
2. 求最小值，将所有值初始化为无穷大，找到 DP 的起点（边界），手动赋值；
3. 求方案数，将所有值初始化为 0 ，找到 DP 的起点（边界），手动赋值，一般为 1 。
   在还没有熟悉的时候，建议认真找到所有边界值，并给它们赋上初值，这样的方式肯定是正确的。
   熟悉了以后，针对某些特定的题目，可以根据经验，遵循 不影响最终答案 的原则，省略部分赋值的步骤。
4. 状态转移方程涉及到 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() 

为什么选的状态转移 方程 是 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 个物品里选剩下的就行了。

#includeusing 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]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。

#includeusing 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 ] 表示达到当前钱数时，已经求出的方案数；

每一种菜都可以选择吃和不吃

#includeusing 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时，说明当前方案已经成立，所以方案总数加 1for (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]

#includeusing 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).约翰只能整包购买，

他最多可以运回多少体积的干草呢？

虽然问的是体积，但可以将这个问题看成价值和体积相等

这样就和背包问题 一 模 一 样 了！

#includeusing 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/

麦克风网