01背包动态规划算法入门

9654

咱今年九月考完CSP就要退役了，初三一整年估计都不会怎么碰了（
所以想着给有需要的人写个教程（
贪心啊二分啊学得都不是很好，就动态规划学挺好的（
热知识：这个人学得最烂的，居然是拓扑排序这种这么简单的东西，连图论都学得比这玩意好
所以今天来讲动态规划了（
鉴于我是蒟蒻，树形动规和插头动规都没学过，背包动规又很经典，今天下午就写01背包动规的了（

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

因为不喜欢论坛的分割线所以手动分割线了

动态规划是什么？
动态规划（Dynamic Programming,DP）是一种算法，常用于求最优解且对中间步骤无过多要求的题（如果中间步骤都要输出那肯定是建议拿搜索算法写的），通常会列出各种可能的状态然后找出最大值/最终值（具体要看是什么题目）。这一算法的原理就是将复杂的问题转化为若干个子问题，最后将子问题的答案合并并加以处理得出答案。
背包动态规划是什么？
背包动态规划，大多数情况用于处理在容量有限情况下存储物价值的最大化。“背包”一词出自背包动态规划最经典的例子：一个旅行者的背包容量为m kg，一共有n件物品可供他装入背包，每件物品都有各自的重量和价值。求背包内物品的最大价值。
动态规划和贪心算法的区别？
贪心算法（Greedy对，国外就是这么叫的，这个词本义是“贪心的”），通常用于求最优解，但因为贪心算法只适用于局部最优解，有时可能无法使用贪心算法（毕竟局部最优解不一定是全局最优解）。一般来说，可以用贪心算法解决的题目都可以使用动态规划解决，但可以使用动态规划解决的问题不一定能用贪心算法。（一个例子：我在学动规之前用贪心交了背包问题，结果是部分正确，也就是说一些情况贪心是无能为力的）如果一道题目既能用贪心和动规，有时候会选择贪心，因为动规需要额外的dp数组，在毒瘤出题人空间卡得很死的情况下有MLE的风险。
01背包动态规划是什么？
是背包动态规划的一个子类，对于一个物品只有“装”和“不装”两个选择，每种物品均只有一件。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

那么我们就通过一道例题来具体地了解这个算法吧！

例题
一位旅行者的背包一共能装 m kg 的东西，现在一共有 n 件物品，每件物品都有各自的重量 wi 和价值 ci ，求背包内物品的最大价值。
输入一行2个整数 m,n ，含义如题目所；接下来的 n+1 行，每行2个整数 wi,ci ，含义如题目所示。
懒，不想写数据范围，这里随便给个0<n<=200吧。

动态规划一般会有一个 dp 数组，而这个 dp 数组就用于表示各种状态。在这题中，dp[j] 代表遍历（注意是遍历而不是装入）第 i 个物品、背包内物品总重量为 j 时背包内物品的最大总价值。看网上很多人说最终输出的应该是 dp[n][m] ，emmm确实没错但这里的dp[n][m]可就和遍历第 n 个物品背包内物品总重为 m 时的最大价值没关系了，因为在动规结束后会排序，这里的 dp[n][m] 只是在取 dp 数组的最大值而已。

鉴于喵玉并没有表格工具，我只能手打背包的表格了（
太大的数咱不好算，这里取 m=5，n=3的情况。三个物品的信息如下：
w  c
1   3
4  2
3  6
很容易分析出最大的价值为 9 ，也就是拿第一个和第三个物品，那么具体的实现步骤呢？

（今天估计是写不完了，找时间再填坑，反正也不会这么快有人看的罢）

苍天的园艺师

表	格
有	的
，	点
高	级
模	式
看	看

定难军节度使

  “表格”：用于创立一个毫不美观的表格，代码如下：

1. [table=100,Red]（意为创建宽度100像素，底色为红色的表格）
   
2. [tr][td] [/td][td] [/td][/tr]（tr表示每一行的起止，td表示每一列的起止。）
   
3. [tr][td] [/td][td] [/td][/tr]
   
4. [/table]（表格结束）

复制代码

  效果如下
  更多高级模式知识请见： 【持续更新】喵玉殿文章排版手册（高级模式已更新完毕）

星阁少女

想起「不好的回忆」
（dp本身还是很不错的，简单也好用，但是dp的各种阴间变体和优化……）

Gunder

同九月退役