题解 P1048 【采药】

*//我其实早就想写一篇动态规划的文章了，虽然我也很弱……我的思路会和市面上的一些辅导书不同，我直接从背包问题入手，主要面对初学者，讲的比较啰嗦，还会涉及很多优化供学有余力者学习。一旦弄懂了这类比较典型也比较难的问题，动态规划的能力会显著提升。 文章里可能会有纰漏，希望大家帮我指出，~~但是请不要嘴臭~~* # 动态规划定义 ~~没用，想看自行百度（滑稽~~ ---------- # 一些基本知识和dp（动态规划）的基本认识 ## - 最优化原理和无后效性原则 ## 作为一个弱省蒟蒻，我的粗鄙的理解就是“现在要干的事对之前没有影响而且是最好的”，这也是符合我们的认知规律的。比如说，我们小学时有接触过一类题（当时虐的年幼的我死去活来） >小明的妈妈要看电视剧，所以小明必须艰苦创业自力更生（雾）。小明早上要干许多事，比如烧水，开电脑luogu签到，上厕所。烧水需要5分钟，上厕所需要2小时（真实），开电脑需要1小时，怎样安排用时最短？ 首先，在生活中，现在做的事肯定不会影响过去（~~起码暂时不会~~ ） ，同样未来做的事也不会影响到现在，这就叫做**无后效性原则**。 那么什么是最优化呢？比如说我们已经开始烧水，那我们现在应该干什么呢，很显然是开电脑，这样我们上完厕所后水也烧好了，电脑也开了（~~痔疮也有了~~ ）。这就是**最优化原理**，我们只要最好的。 ## - 记忆化搜索 ## 表面高大上，但是很多人在做水题的时候早就基本掌握这个思想了。 > N！即1 * 2 * 3 ... * N,现在，我们求99！，100！，101！怎么办呢？ ~~**显然**~~（粗鄙之言），我们只需要算出99！，就不需要再从头计算了，因为100！即是99！ * 100。 > 如果我要求的是1！，2！...N！呢，并且要求在全部计算完之后输出答案？ 显然（逃），我们需要开一个a[101]数组，去保存答案最后输出。这样的话，问题就简单了，我们求N！，只需要知道(N - 1)！，求（N - 1）！，只需要知道（N - 2）！ ……以此类推，我们只需要知道1！ = 1，我们便可以推出2！，进而推出3！……而不需要每次都从头计算。我们将算出的1！，2！……存入a数组，不仅要作为答案输出，还要继续使用它，就好像我们将1！……记下了一样，因此叫记忆化。 ### 记忆化搜索中的dp思想 ### 首先，求N！的过程是满足最优化和无后效性的，所以才能想到这道题可以用dp（虽然好像并没有明确的选择最优，但是我们由(N - 1）！得出N！时只有一个选择—— *N，我们别无选择♂时的唯一一个选择，就可以认为是最优的。 作为让OI选手头疼的拦路虎，状态设计和转移方程无数次令我自闭。其实，只要做题时勤于思考，这种思维方式是可以逐步形成的。 上述问题我们仅用了一层循环便解决了问题（仅仅举例，高精度等问题自己把控），既然说是dp，我们该怎样设计状态和书写转移方程呢？ 在dp中，有种思想特别有用，这种思想叫做逆推（并不适用于所有题），这道题我们不妨逆推。 上文中，我们已设计好了状态（即由1！求2！进而求3！……），大概是下面这个样子的  进而状态转移方程也得到了：a[N] = a[N - 1] * N; # 0-1背包 我以前是真的觉得dp超级难啊，自从钻研了半个多月之后，~~嗨，效果还真好！我们全家都用它！~~ ## 题目 > 她，是无数男人追求不到的纯情少女。 > 他，是曾经的雇佣兵王。 > 或许是冥冥中的缘分使两人相识，他爱上了她。为了保护她，他无意中得罪世界最大恐怖势力僞窿辣条集团（~~雾~~。 > 现在，他只有最后一点钱，再也不能说那句熟悉的”买！都给我买“了，为了保护心爱之人，他必须用有限的钱买尽可能多的辣条，僞窿辣条集团故意难为他，将每包辣条都标上了不同的价格，每包有不同的根数，他很伤心，请你帮帮他。 有M元，共有N种辣条，第N种有v[n]根辣条，价格为w[n]，求最大可买到的辣条数。 ## 贪心算法气得爆哭 我们可以轻松构造一批数据来证明贪心算法不可行。 > 只有四种辣条，第一种七元，有九根，第二种六元，有五根，第三种七元，有八根，第四种六元，有六根，我们的雇佣兵王只有19元（~~好惨一男的~~ 很明显，第一种和第三种明显比第二种和第四种划算，所以我们如果贪心的话，一定是先选一三，但是选一二四才是真正的答案。为什么呢？因为贪心目光短浅，他选的只是当前的最划算的辣条，而不是全部种类的辣条都考虑，这就导致了会有空间被浪费。用上一章的话来说，贪心算法做的话不满足最优化原理。 **提示** . 通常情况贪心和dp题是很容易看出来的，但是究竟是用贪心还是用动归需要自己证明，这是个很重要的步骤，上文我构造的数据其实是对贪心不可行的证明，我在上一章给出了dp可行的证明，希望大家可以举一反三，证明一下此题符合最优化原理和无后效性原则，进而证明此题可以dp。 ## dp解背包问题 背包问题的状态设计和转移方程对于初学者来说是有难度的，我在这里~~假装~~ 推理一下。 首先，因为是01背包，每种辣条只有一包，对于某种辣条，我们仅有两种选择——买或不买，最优选择一定在这两者中。 其次，我们要知道第N种辣条取或不取哪种情况更优，我们就必须先知道第N - 1种辣条取与不取哪种更优，为什么呢？因为我们先取的是第N - 1种，如果我们第N - 1种取的是最优解，那么我们取第N种时的得到的最优解一定比第N - 1不是最优解时得到的要好，我们可以像下图这样理解 如果我们简单的通过好/坏的多少来判断好坏，请问黑色和**绿色**（~~滑稽~~）哪个更好呢？当然是黑色，同理，我们从1选到N，一定是每一包都选最优解咯。 那么，每种辣条的两种选择（取/不取），我们可以把它们转化成：取，则相当于求用M - w[i] （0 <= i <= N）元买前N - 1种辣条的最优解；不取， 则相当于我们用M元买前N - 1种辣条。为什么取的时候要用M - w[i] 元取呢？因为我们用M - w[i] 元取，就相当于已经把第N种辣条的钱留出来了。类似于我们去饭店恰饭，如果我们提前订好桌，就不必担心没有座位了。 这个推论告诉我们，我们求N的最优解必须知道用m元买N - 1种辣条与用m -w[N] 元买N - 1种辣条哪个更优。但是编号再靠前的辣条我们怎么考虑呢？我们不知道后面有几包辣条取几包不取，所以我们就无法确定到底要留多少钱，既然这样，我们不如把每种辣条从1 — w元都考虑一遍，反正雇佣兵王有的是钱（~~兵王:“胡说！！！”~~）。 （我相信在这里一些同学已经看出了些许猫腻，其实有些物品我们并不需要算出1 — w的最优解，因为排在它编号之后的辣条价格总和可能根本达不到w元，这是本章末会讲到的一个常数优化） 我们可以发现，我们不仅需要考虑每种辣条，还需要考虑每种辣条在1 — w时的解，这么说来，我们需要一个二维数组dp[ i ][ j ]（i为第i种辣条，j为有j元）来保存我们的“记忆”（不错，就是记忆化搜索的记忆）。我们再用w[ i ]储存第i种辣条的价格，用v[ i ]储存第i种辣条的根数，这样，我们就可以用上文推出的东西来写出转移方程了 ``` dp[i][j] = max(dp[i - 1][m], dp[i - 1][m - w[i]] + v[i]); ``` 为了便于理解，接下来我会给出一个dp的模拟过程。但是在这之前我希望同学们可以自己先推一遍，这是有极大的好处的，我不建议初学者直接跳过。 |钱数/根数 | 1 | 2 | 3 | 4| 5| 6| 7 | 8 | 9| 10| 11| 12 | 13| 14| | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 3/1| 0| 0 | 1| 1 |1 | 1| 1| 1 | 1 |1 |1 | 1 |1 | 1 | | 8/10| | | | | | | | | | | | | | | | 1/1| | | | | | | | | | | | | | | | 4/40| | | | | | | | | | | | | | | | 7/25 | | | | | | | | | | | | | | | 该图即为dp数组，横行为价格与辣条根数(i)，比如3/1表示第一种辣条每包三元，每包一根。竖列为钱数(j)。 dp[ 2 ][ 1 ~ N]: |钱数/根数 | 1 | 2 | 3 | 4| 5| 6| 7 | 8 | 9| 10| 11| 12 | 13| 14| | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 3/1| 0| 0 | 1| 1 |1 | 1| 1| 1 | 1 |1 |1 | 1 |1 | 1 | | 8/10|0 | 0 | 1| 1 |1 | 1|1 |10 |10 |10 | 11 | 11 |11 | 11 | | 1/1| | | | | | | | | | | | | | | | 4/40| | | | | | | | | | | | | | | | 7/25 | | | | | | | | | | | | | | | dp[ 3 ][ 1 ~ N]: | |1 | 2 | 3 | 4|5 |6 |7 |8 |9 |10 |11 |12 |13 |14 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 3/1 | 0 |0 |1 | 1 |1 | 1 | 1 | 1 | 1| 1 |1 |1 | 1 |1 | | 8/10|0 | 0 | 1| 1 |1 | 1|1 |10 |10 |10 | 11 | 11 |11 | 11 | | 1/1|1 | 1 | 1 | 2 | 2 | 2| 2 |10 |11 |11 |11 |12 |12 |12 | | 4/40| | | | | | | | | | | | | | | | 7/ 25| | | | | | | | | | | | | | | dp[ 4 ][ 1 ~ N]: | |1 | 2 | 3 | 4|5 |6 |7 |8 |9 |10 |11 |12 |13 |14 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 3/1 | 0 |0 |1 | 1 |1 | 1 | 1 | 1 | 1| 1 |1 |1 | 1 |1 | | 8/10|0 | 0 | 1| 1 |1 | 1|1 |10 |10 |10 | 11 | 11 |11 | 11 | | 1/1|1 | 1 | 1 |2 | 2 | 2| 2 |10 |11 |11 |11 |12 |12 |12 | | 4/40| 1 | 1| 1 | 40 |41 |41 | 41| 42 | 42 | 42 |42 | 50|51 |51 | | 7/ 25| | | | | | | | | | | | | | | dp[ 5][ 1 ~ N]: | |1 | 2 | 3 | 4|5 |6 |7 |8 |9 |10 |11 |12 |13 |14 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 3/1 | 0 |0 |1 | 1 |1 | 1 | 1 | 1 | 1| 1 |1 |1 | 1 |1 | | 8/10|0 | 0 | 1| 1 |1 | 1|1 |10 |10 |10 | 11 | 11 |11 | 11 | | 1/1|1 | 1 | 1 | 2 | 2 | 2| 2 |10 |11 |11 |11 |12 |12 |12 | | 4/40| 1 | 1| 1 | 40 |41 |41 | 41| 42 | 42 | 42 |42 | 50|51 |51 | | 7/ 25| 1| 1 |1 |40 |41 |41 |41 |42 |42 |42 |65 |66 |66 |66 | (已修正，~~鬼知道我打的破表为什么第一次不能显示~~) 这样，我们便得到了最优解dp[N][M] = 66。 我们一定要把数组开成dp[ 1 ~ N][ 1 ~ M]的，把0都留下，不然可能会数组越界。 练习题 [采药](https://www.luogu.org/problemnew/show/P1048) 文章最末附上我的AC代码 # 一些小优化 # 1.滚动数组 这是一个空间优化，可以将二维数组降至一维，在许多位数较高的背包问题中有奇效，建议学习一下。 ## 原理 这个优化其实可以通过对转移方程的观察得出。 ```cpp dp[i][j] = max(dp[i - 1][m], dp[i - 1][m - w[i]] + v[i]); ``` 我们发现在求dp[i][j]时用到的状态全部来自dp[i - 1][j]，emmmmmm，根据最优化原理和无后效性原则，我们可以知道此时的dp[i - 1][j]已经是最优的而且已经没有用了，所以我们可以直接把dp[i][j]上的内容覆盖到dp[i - 1][j]上去。这样的话，我们只需要一个一维数组就可以解决这个问题了，这是一个对空间的极大优化，空间复杂度由原先的O（N * M）降至了现在的O(M)，但是，请大家观察下面两个代码，看看有什么不同。 70 3 71 100 69 1 1 2 这是输入数据 代码一： ```cpp cin >> t >> m; for(int i = 1; i <= m; i++) cin >> w[i] >> v[i]; for(int i = 1; i <= m; i++){ for(int j = t; j >= 1; j--) dp[j] = max(dp[j - w[i]] + v[i], dp[j]); } cout << dp[t]; ``` 输出 3 代码二： ```cpp int main（）{ cin >> t >> m; for(int i = 1; i <= m; i++) cin >> w[i] >> v[i]; for(int i = 1; i <= m; i++){ for(int j = 1; j >= t; j++) dp[j] = max(dp[j - w[i]] + v[i], dp[j]); } ``` 输出0 为什么呢？ 不知大家发现没有，这两个代码的第二层循环的顺序改变了，也就是对钱数的循环顺序变了，为什么一个小小的操作会有这么大的影响呢？因为我们在更新dp[i]数组时，用的是dp[i ]和dp[i - w[i]]这两个状态，假如我们从1更新到M，那么当我们更新dp[i]时，dp[i - w[i]]已经被更新过了，它已经不是原来的那个dp[i - w[i]]了，很有可能dp[i - w[i]]已经买了一包第i种辣条，然后我们更新dp[i]时调用dp[i - w[i]]，又买了一包一样的辣条，这不符合01背包。（虽然不符合01背包，但是大家一定也看出来了，这符合一个物品可取多次的情况，即下一章我会讲到的完全背包问题） 接下来，我为大家模拟一遍这个程序 假设一种辣条的费用3，根数为1，第二种费用为8，根数为10。初始dp数组被初始化为0。 ```cpp dp[15] = dp[12] + 1; dp[14] = dp[11] + 1; dp[13] = dp[10] + 1; ...... //这一轮更新过后，dp[3~15] = 1， 其余为0； //第二轮更新： dp[15] = dp[7] + 10; dp[14] = dp[6] + 10; dp[13] = dp[5] + 10; ...... 此时dp[1~2] = 0, dp[3~7] = 1, dp[8~10] = 1, dp[11 ~ 15] = 11。 ``` 可以发现，这和上文中二维数组的模拟结果是一样的。 但是这种方法有一个弊端，就是输出到底买了哪几种辣条时不便。 # 2.常数优化 ## 1. 优化一 我们在循环的时候，我们可以发现钱数少于w[i]的情况是不会被更新的，因为此时压根买不起第i种辣条，如图  我们发现，划横线的那些是完全继承了上次循环的状态。 所以，我们再循环时可以改成从w[i] ~ M。 ```cpp for(int i = 1; i <= m; i++){ for(int j = t; j >= w[i]; j--) dp[i] = max(dp[j - w[i]] + v[i], dp[j]); } ``` ## 2.优化二 这个优化比上一个优化更明显，但是稍微难理解。 由于只需要最后dp[m]的值，倒推前一种辣条，我们只要知道dp[m-w[n]]即可。以此类推，对以第j种辣条，其实只需要知道到dp[m-sum{w[j~n]}]即可。这在钱数较大的时候是比较有用的。代码希望大家自己理解透彻后实现，是比较简单的。 ## 01背包讲完了！，你是否有了一些更深层次的理解呢？或许你有一些和我不同的看法，欢迎联系我。01背包非常非常非常重要！一定要完全理解鸭，我们后面会讲到的几种背包问题，都可以变形为01背包，多花一些时间在01背包上真是受益匪浅啊。 AC代码（优化后） ```cpp using namespace std; #include <bits/stdc++.h> int t, m, dp[1010], w[110], v[110]; int main(){ ios::sync_with_stdio(false); cin >> t >> m; for(int i = 1; i <= m; i++) cin >> w[i] >> v[i]; for(int i = 1; i <= m; i++){ for(int j = t; j >= w[i]; j--) dp[j] = max(dp[j - w[i]] + v[i], dp[j]); } cout << dp[t]; return 0; } ```