初级天翼
谁有各种背包和动态规划的课后讲义？
采纳讲义最完整，讲义最多的童鞋
刘意阳在2022-09-27 19:04:58追加了内容
越快越好
刘意阳在2022-09-27 19:05:11追加了内容
越快越好
刘意阳在2022-09-27 19:07:29追加了内容
禁止水
刘意阳在2022-09-28 18:00:47追加了内容
顶顶顶
刘意阳在2022-10-03 08:44:25追加了内容
顶顶顶
初级启示者
666
初级天翼
动态规划思想
一、动态规划概念：
动态规划（dp）是研究多步决策过程最优化问题的一种数学方法。在动态规划中，为了寻找一个问题的最优解（即最优决策过程），将整个问题划分成若干个相应的阶段，并在每个阶段都根据先前所作出的决策作出当前阶段最优决策，进而得出整个问题的最优解。即记住已知问题的答案，在已知的答案的基**上解决未知的问题。
在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相**的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。可以自行创建一个动态规划表dp,dp一般是个数组，可以是一维也可以是二维数组，根据题中的需要，然后将子问题的最优解填入其中，方便在求解之后的子问题时可以方便调用，进而求出整个问题的最优解。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
动态规划有两种实现方法，一种是递推，另一种是记忆化搜索。两种方法时间复杂度完全相同，但是，递推的效率要比记忆化搜索高不少，而且以后的大量优化技巧都建立在递推上（**动数组、单调队列、斜率优化……）。所以，我们一般用递推来写动态规划。
二、动态规划的**质：
(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效**：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不**的，一个子问题在下一阶段决策中可能被多次使用到。（该**质并不是动态规划适用的必要条件，但是如果没有这条**质，动态规划算法同其他算法相比就不具备优势）
三、动规解题的一般思路：
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效**。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
四、解题步骤：
拆分问题；
定义状态并找出初状态；
状态转移方程。
五、算法实现的步骤：
1、创建一个一维数组或者二维数组，保存每一个子问题的结果，具体创建一维数组还是二维数组看题目而定，基本上如果题目中给出的是一个一维数组进行操作，就可以只创建一个一维数组，如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值，比如背包问题中的不同物体的体积与总体积，找零钱问题中的不同面值零钱与总钱数，这样就需要创建一个二维数组。注：需要创建二维数组的解法，都可以创建一个一维数组运用**动数组的方式来解决，即一位数组中的值不停的变化，后面会详细徐叙述
2、找到初始条件，设置数组边界值，一维数组就是设置第一个数字，二维数组就是设置第一行跟第一列的值，特别的**动一维数组是要设置整个数组的值，然后根据后面不同的数据加进来变幻成不同的值。
3、根据初始条件或边界条件，找出状态转换方程，也就是说找到每个状态跟他上一个状态的关系，根据状态转化方程写出代码。
4、返回需要的值，一般是数组的最后一个或者二维数组的最右下角。
初级启示者
初级天翼
666
初级启示者
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，**数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金**问题、资源分配问题、最短路径问题和复杂**可****问题等中取得了显著的效果
原理
动态规划问世以来，在经济**、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存**、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便 。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线**规划、非线**规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
概念引入
在现实生活中，有一类活动的过程，由于它的特殊**，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法 。
基本思想
动态规划算法通常用于求解具有某种最优**质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相**的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式 。
基本概念
-
多阶段决策问题
如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策（采取措施），一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题 。
各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果 。
-
动态规划问题中的术语
阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的 。
状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点 。
无后效**：我们要求状态具有下面的**质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个**质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个**质称为无后效**。
决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效**，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史 。
决策变量的范围称为允许决策集合 。
策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合 。
允许策略集合中达到最优效果的策略称为最优策略 。
给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k))与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程 。
最优化原理：作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略” 。
最优**原理实际上是要求问题的最优策略的子策略也是最优 。
基本结构
多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法 。
适用条件
任何思想方法都有一定的局限**，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效** 。
-
最优化原理（最优子结构**质）
最优化原理可这样阐述：一个最优化策略具有这样的**质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构**质 。
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向**，又称为无后效** 。
-
子问题的重叠**
动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间 。
分类
动态规划的数学模型。根据决策过程的演变是确定**的还是随机**的。可分为确定**决策过程和随机**决策过程。另外。也可按时间参量是离散的或是连续的变量。分为离散决策过程和连续决策过程。组合起来就有离散确定**．离散随机**．连续确定**．连续随机**四种决策过程模型 。
对于确定**的决策过程。问题中下一段的状态已由当前段的状态及决策完全确定。对于随机**决策过程。它与确定**决策过程的区别在于下一段的状态并不能由当前段的状态及决策完全确定。而是按某种概率分布来决定下一段的状态。这种概率分布是由当前段的状态和决策完全确定。
局限**
动态规划对于解决多阶段决策问题的效果是明显的，但是动态规划也有一定的局限**。首先，它没有统一的处理方法，必须根据问题的各种**质并结合一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急剧增大。因而，受计算机的存贮量及计算速度的限制，当今的计算机仍不能用动态规划方法来解决较大规模的问题，这就是“维数障碍"
初级启示者
贪心算法1：容量问题+排队问题课后讲义（火箭v2）
贪心算法1：容量问题+排队问题
一、课堂内容
- 贪心算法的基本思想
在对一个问题求解时，总是做出在当前看来是最好的选择。也就是说，把一个较复杂的问题分解成若干子问题，对于每个子问题来说， 不从整体最优上加以考虑，只做出在某种意义上的局部最优解。
通过每次得到局部最优解答，逐步推导出问题，进而得到全局最优解。
通俗地来讲，就是怎么做有利就怎么做。
- 贪心问题的解决总是伴随着排序，我们以选择尽量优的解的原则，将事物按照最优的解在最前的顺序排好，然后依次选取最优选择，构成整体最优解。
二、课堂练习详解
1266 摘取苹果2
分析： 摘苹果花的总力气是有限的，因此我们希望每次花尽量小的力气摘苹果，则自然想到按照摘苹果花的力气从小到大排个序。但是摘苹果的时候还要考虑到高度，排序的时候要把每个苹果的高度也带上，所以我们考虑使用结构体排序，将摘苹果花的力气和苹果的高度作为结构体成员变量。
按所花力气从小到大排好序后，我们只要按顺序尝试摘每个苹果（能摘就摘）：如果当前的苹果高度能够达到并且剩的力气还够摘就摘。
1283 最高得分（maxvalue）
分析： 由于总时间有限，而每秒固定能摘取一颗水晶珠，所以要得到最大价值，肯定是优先摘单颗价值高的水晶珠。因此我们按照水晶珠的平均价值来排个序。
按照水晶珠的平均价值从大到小排好序之后，我们只要按照顺序摘取水晶珠就可以了。对于当前某种水晶珠，如果剩余时间足够摘取，就把当前这种水晶珠全部摘取，否则剩余时间里能摘多少就摘多少。
4467 最小等待时间(waiting)
分析： 前面的人付款的时候，后面的所有人都在等待，因此我们考虑让付款等待时间短的人先付款，能够使得所有人的等待时间变短。
按照等待时间从小到大排好序之后，计算每个人需要花的等待时间（第i个人的等待时间是前i-1个人所花时间之和），然后累加即可。
1453 接水问题
分析： 本题按照题目所述，当m个水龙头都有人用时，下一个人应该等待，m个水龙头中哪个最先空出来，就去哪个水龙头接水。
一共n个人，前m个人先安排在1~m号水龙头接水，后面每个人在选择水龙头的时候，都是选择一个最先空出来的，可以用数组将每个水龙头的接水结束时间记录下来，每次选择的时候是选择结束时间最早的水龙头接水。
初级启示者
贪心算法1：容量问题+排队问题课后讲义（火箭v2）
贪心算法1：容量问题+排队问题
一、课堂内容
- 贪心算法的基本思想
在对一个问题求解时，总是做出在当前看来是最好的选择。也就是说，把一个较复杂的问题分解成若干子问题，对于每个子问题来说， 不从整体最优上加以考虑，只做出在某种意义上的局部最优解。
通过每次得到局部最优解答，逐步推导出问题，进而得到全局最优解。
通俗地来讲，就是怎么做有利就怎么做。
- 贪心问题的解决总是伴随着排序，我们以选择尽量优的解的原则，将事物按照最优的解在最前的顺序排好，然后依次选取最优选择，构成整体最优解。
二、课堂练习详解
1266 摘取苹果2
分析： 摘苹果花的总力气是有限的，因此我们希望每次花尽量小的力气摘苹果，则自然想到按照摘苹果花的力气从小到大排个序。但是摘苹果的时候还要考虑到高度，排序的时候要把每个苹果的高度也带上，所以我们考虑使用结构体排序，将摘苹果花的力气和苹果的高度作为结构体成员变量。
按所花力气从小到大排好序后，我们只要按顺序尝试摘每个苹果（能摘就摘）：如果当前的苹果高度能够达到并且剩的力气还够摘就摘。
1283 最高得分（maxvalue）
分析： 由于总时间有限，而每秒固定能摘取一颗水晶珠，所以要得到最大价值，肯定是优先摘单颗价值高的水晶珠。因此我们按照水晶珠的平均价值来排个序。
按照水晶珠的平均价值从大到小排好序之后，我们只要按照顺序摘取水晶珠就可以了。对于当前某种水晶珠，如果剩余时间足够摘取，就把当前这种水晶珠全部摘取，否则剩余时间里能摘多少就摘多少。
4467 最小等待时间(waiting)
分析： 前面的人付款的时候，后面的所有人都在等待，因此我们考虑让付款等待时间短的人先付款，能够使得所有人的等待时间变短。
按照等待时间从小到大排好序之后，计算每个人需要花的等待时间（第i个人的等待时间是前i-1个人所花时间之和），然后累加即可。
1453 接水问题
分析： 本题按照题目所述，当m个水龙头都有人用时，下一个人应该等待，m个水龙头中哪个最先空出来，就去哪个水龙头接水。
一共n个人，前m个人先安排在1~m号水龙头接水，后面每个人在选择水龙头的时候，都是选择一个最先空出来的，可以用数组将每个水龙头的接水结束时间记录下来，每次选择的时候是选择结束时间最早的水龙头接水。
初级启示者
贪心算法2：数字的拆分、删除与重组课后讲义（火箭v2）
贪心算法2：数字的拆分、删除与重组
一、课堂内容
1. 数字的拆分
将一个大数拆分成小数字的和，如果要求拆分的数量尽量少，则贪心的思路是尽量拆成大的数字，值不够了再往小的数字去拆。
2. 数字删除固定位数
把一个数字删除固定位数，要求最后剩的数字最大，不能只是删除所有小的数字。比如：2131要求删2位，如果是删除两个1，会得到23，但其实删掉21，剩下31才是最大的。
因为删除后的数字位数是确定的，所以正确的贪心思路应该是让首位数字尽可能大。
2. 数字组合位数
把若干个数字组合成一个新的数字，使其最小。不能够只是把短的数字或者小的数字放前面，比如2和11组合，把11放前面组成的数字更小。
此时要考虑的是数字组合之后数值更小，比如a和b组合，我们应当比较ab和ba的大小，来确定谁放前面。
二、课堂练习详解
1418 超市结账
分析： 此题思路很明确，要使钞票的张数最少，则应优先使用大额的钞票。
我们可以将不同的面额存进数组中，之后从前往后遍历数组，优先选择使用**前的面额钞票（当前面额的钞票能用几张就用几张），剩余的钱使用后面面额的钞票（都是能用几张就用几张）。
1412 数字删除游戏
分析： 首先输入的数字位数过大，需要采用字符串的形式输入。
将数字删除m位，剩下的位数是固定的（原来的位数-m位），对于相同位数的数字来说，高位大的数字更大，所以应当使删除后的数字高位尽可能大。
所以在删除每一个字符时我们采取的操作是：
从高位看起，如果有一个数字比后面的的数字小，就把它删除，后面的数字自动补上，即可以使得这一位数字变大。
这样可以保证m次操作之后高位的数字尽量大。
2787 数字组合
分析： 从n个数字中选m个数字，那么我们应当选择尽量短的m个，才可以保证最后数字的总位数最短，但是光**长度去选m个不一定准确，因为可能有数字位数相同。比如在选第m个数时，有很多个长度相同的，该选哪一个？这里我们就要考虑数字本身的大小，比如“12”和“34”，明显选“12”更小。
因此我们在选择m个数的时候，首先考虑长度，选长度小的，长度相同时，选字符串字典序较小的。
选完m个字符串之后，是不是就直接输出了呢？也不是。直接输出的话，是先输出长度短的，再输出长度长的，但是长度短的排在前不一定比长度长的排在前更小，比如“121”和“12”组合，就是长的在前（12112）更小。因此这里要对m个数再一次排序，考虑数字组合的顺序，比如a和b组合，谁放在前面更小，就把谁放前面，此处比较时，我们可以比较a+b与b+a的值，因为数字位数是确定的，只要比较下组合之后数字的大小即可。
初级启示者
贪心算法3：区间问题+其它贪心（火箭v2）
贪心算法四：区间问题课后讲义
一、课堂内容
1. 区间覆盖类问题
对于区间覆盖类的问题（区间可能有重叠，问被覆盖的区间总大小），解题时考虑按照每个区间的起点从前往后排序，然后遍历每个区间，判断当前区间是否与前一个区间相连（判断当前区间的起点在上个区间的终点之前还是之后）。
2. 活动安排问题
限定的场地要安排多个活动，不同的活动间时间可能会冲突，怎么才能安排尽量多的活动？
按照活动的结束时间从小到大排序，尽量安排结束时间早的活动，这样才能为后续安排活动留下更充足的时间。
3. 建立模型
对于某些贪心问题，直接想思路并不好想，需要对问题进行分析，建立数学模型，在此基**上确立贪心思路。
4. 验证贪心思路
对于某个问题贪心思路的正确**验证，我们可以尝试按照此思路是否能举出反例，这是一个很好的筛选贪心思路的方法。
二、课堂练习详解
2775 泥泞的小路
分析： 先按照小路起点的先后排好序，考虑总是先铺满前面的路。在铺某一段路时，可能这段路某些部分已经被前面的木板覆盖了，我们考虑以下3种情况：
1）当前的路没有被覆盖：
2）当前要铺的路部分被覆盖：
3）当前要铺的路完全被覆盖：
则在铺第i条路时，我们需要考虑从哪里开始铺？需不需要铺？
1398 教室安排
分析： 对于本题，我们可能会从以下方面考虑：
1）尽量先安排持续时间短的活动
2）尽量先安排开始时间早的课程
3）尽量先安排结束时间早的活动
这些考虑都是合理的，但是经过举例验证，发现只有第3种策略是正确的。
反例：
1）3个班课：1:00–9:00 8:00–11:00 10:00–18:00
如果先安排持续时间短的课（第2个），则第1个和第3个都安排不了。
2）3个班课：1:00–18:00 8:00–11:00 14:00–18:00
如果先安排开始时间早的课（第1个），则第2个和第3个都安排不了。
3）尽量先安排结束时间早的活动，举不出反例，我们可以这样考虑它的合理**：先安排结束时间早的课，则会遗留更多的时间以供安排，这对我们安排尽量多的课程是有利的。
1184 乘船过河（ship）
分析： 船每次最多运两人过河，要使船的数目最少，则每次发船应当尽量让两人过河。
由于载重有限制，每次发船我们考虑让最重的人先上船，然后能再带一个人，就再带一个人。
这个人我们只需要考虑能不能带走剩下的人里最轻的人即可。如果最轻的人都带不走，其他人自然也带不走。
初级启示者
贪心也行吧
也是动态规划的一种
（网卡了，多发了一个 贪心算法1）
初级天翼
初级天翼
动态规划真的没啥哎
初级启示者
能给我点豆吗？
我很穷的
初级天翼
初级启示者
初级启示者
