规则类动态规划

动态规划----流⽔线调度问题问题的描述：n个作业{1，2，…，n}要在由2台机器M1和M2组成的流⽔线上完成加⼯。

每个作业加⼯的顺序都是先在M1上加⼯，然后在M2上加⼯。

M1和M2加⼯作业i所需的时间分别为ai和bi。

流⽔作业调度问题要求确定这n个作业的最优加⼯顺序，使得从第⼀个作业在机器M1上开始加⼯，到最后⼀个作业在机器M2上加⼯完成所需的时间最少。

调度规则(1 ) 把全部ai和bi分类成⾮降序列，ai和bi分别是第i个作业在两个机器上所需要的时间。

(2 ) 按照这⼀分类次序考察此序列: 如果序列中下⼀个数是aj 且作业j还没调度,那么在还没使⽤的最左位置调度作业j ; 如果下个数是bj 且作业j还没调度,那么在还没使⽤的最右位置调度作业j ; 如果已经调度了作业j,则转到该序列的下⼀个数。

算法主要利⽤Johnson不等式原理，对于所有的a步骤和b步骤的时间从⼩到⼤排序。

如果合并序列中拿出的元素属于a集合，则将其所属的job作为第⼀个job执⾏；如果属于b集合，则将其所属的job作为最后⼀个job执⾏。

进⾏下⼀个元素的判断，分别作为第⼆、倒数第⼆，依次类推；直到所有job被标记之后退出，获得的job数组就是job的执⾏序列。

例⼦1设 n=4,( a1,a2,a3,a4 ) =( 3,4,8,10 ) 和( b1,b2,b3,b4 ) =(6,2,9,15 ),对这些a和b分类后的序列是( b2,a1,a2,b1,a3,b3,a4,b4 ) = ( 2,3,4,6,8,9,10,15),设σ1,σ2,σ3,σ4是最优调度。

最⼩数是b2, 置σ4 = 2。

下⼀个最⼩数是a1, 置σ1 = 1。

接着的最⼩数是a2,由于作业2已被调度,转向再下⼀个数b1 。

作业1已被调度,再转向下⼀个数a3,置σ2 = 3。

最后剩σ3 是空的,⽽作业4还没调度,从⽽σ3= 4例⼦2：排序的结果( a4,b3,a0,b1,a2,b2,a1,b0,a3,b4 )执⾏顺序为 J4 -> J0 ->J2 ->J1 ->J3。

动态规划方法求解线性规划问题动态规划是一种常用的优化方法，可以用来求解线性规划问题。

线性规划是数学规划的一种重要方法，它通过线性约束条件和线性目标函数来求解最优解。

在实际应用中，线性规划经常遇到大规模问题，传统的求解方法效率较低。

而动态规划方法可以通过将大问题分解为小问题，并利用子问题的最优解来求解整个问题的最优解，从而提高求解效率。

动态规划方法求解线性规划问题的步骤如下：1. 确定问题的状态：将线性规划问题转化为动态规划问题时，需要确定问题的状态。

对于线性规划问题，状态可以是决策变量的取值范围或者问题的某种特征。

2. 定义状态转移方程：根据问题的状态，定义状态转移方程。

状态转移方程描述了问题从一个状态转移到另一个状态时的转移规则。

3. 确定边界条件：确定问题的边界条件，即问题的初始状态和结束状态。

4. 构建动态规划表：根据状态转移方程和边界条件，构建动态规划表。

动态规划表是一个二维表格，用于存储问题的中间结果。

5. 填充动态规划表：根据状态转移方程和边界条件，填充动态规划表。

填充的过程是从表格的左上角开始，逐行逐列地计算表格中的每个单元格的值，直到填充到右下角。

6. 根据动态规划表求解最优解：根据填充好的动态规划表，可以得到问题的最优解。

最优解可以通过回溯法得到，即从右下角开始，根据动态规划表的值和状态转移方程，逆向推导出问题的最优解。

动态规划方法求解线性规划问题的优点在于可以将大问题分解为小问题进行求解，并且可以利用子问题的最优解来求解整个问题的最优解。

这样可以大大提高求解效率，特别是对于大规模问题来说。

此外，动态规划方法还具有较好的可扩展性和灵活性，可以根据问题的特点进行相应的调整和优化。

举例来说，假设有一个线性规划问题，要求在满足一定约束条件的情况下，最大化目标函数的值。

可以将该问题转化为动态规划问题，并按照上述步骤进行求解。

首先确定问题的状态，可以将决策变量的取值范围作为状态。

然后定义状态转移方程，根据问题的约束条件和目标函数，确定状态之间的转移规则。

统筹问题的规律和公式
统筹问题是一种常见的数学问题，它涉及到在有限的时间和资源条件下，如何最优地安排任务以达到目标。

解决统筹问题的方法和规律有很多，以下是一些常见的规律和公式：
1. 线性规划：线性规划是一种常见的数学优化方法，它通过建立线性方程组来描述问题，并求解最优解。

线性规划可以用来解决许多统筹问题，例如资源分配、时间安排等。

2. 动态规划：动态规划是一种解决优化问题的算法，它通过将问题分解为子问题并求解最优解来找到全局最优解。

动态规划可以用来解决许多涉及时间序列的统筹问题，例如背包问题、任务调度等。

3. 模拟退火：模拟退火是一种启发式搜索算法，它通过模拟物理中的退火过程来寻找最优解。

模拟退火可以用来解决许多难以用传统方法解决的统筹问题，例如旅行商问题、调度问题等。

4. 优先级规则：优先级规则是一种常见的统筹方法，它根据任务的紧急程度和重要性来安排任务的优先级。

优先级规则可以用来解决许多时间安排问题，例如会议安排、任务调度等。

5. 关键路径法：关键路径法是一种项目管理方法，它通过确定项目的关键路径和关键任务来安排资源和时间。

关键路径法可以用来解决许多项目管理和工程管理中的统筹问题。

这些方法和规律是解决统筹问题的重要工具，可以根据具体的问题选择合适的方法来解决。

洛⾕——动态规划1.P1057 传球游戏题⽬描述上体育课的时候，⼩蛮的⽼师经常带着同学们⼀起做游戏。

这次，⽼师带着同学们⼀起做传球游戏。

游戏规则是这样的：n个同学站成⼀个圆圈，其中的⼀个同学⼿⾥拿着⼀个球，当⽼师吹哨⼦时开始传球，每个同学可以把球传给⾃⼰左右的两个同学中的⼀个（左右任意），当⽼师在此吹哨⼦时，传球停⽌，此时，拿着球没有传出去的那个同学就是败者，要给⼤家表演⼀个节⽬。

聪明的⼩蛮提出⼀个有趣的问题：有多少种不同的传球⽅法可以使得从⼩蛮⼿⾥开始传的球，传了m次以后，⼜回到⼩蛮⼿⾥。

两种传球⽅法被视作不同的⽅法，当且仅当这两种⽅法中，接到球的同学按接球顺序组成的序列是不同的。

⽐如有三个同学1号、2号、3号，并假设⼩蛮为1号，球传了3次回到⼩蛮⼿⾥的⽅式有1->2->3->1和1->3->2->1，共2种。

输⼊输出格式输⼊格式：输⼊⽂件ball.in共⼀⾏，有两个⽤空格隔开的整数n，m（3<=n<=30，1<=m<=30）。

输出格式：输出⽂件ball.out共⼀⾏，有⼀个整数，表⽰符合题意的⽅法数。

输⼊输出样例输⼊样例#1：3 3输出样例#1：2说明40%的数据满⾜：3<=n<=30，1<=m<=20100%的数据满⾜：3<=n<=30，1<=m<=302008普及组第三题思路： 我们可以先把这个圈展开，那么球是不是就只有从左边传来和从右边传来两种情况呢？ 所以wuli转移⽅程就到⼿啦！！ 再想⼀想，还有两个特殊情况呢，第⼀个和最后⼀个。

⽆奈的加特判喽~~上代码：#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n,m,f[31][31];//f[i][j]表⽰第i个⼈传j次所能获得的次数int main() {cin>>n>>m;memset(f,0,sizeof(f));f[1][0]=1;//设置第⼀⼈为传回来的⼈，传0次（相当于还没穿出去）有1种传回的情况for(int j=1; j<=m; j++)for(int i=1; i<=n; i++) {if(i==1)f[i][j]=f[n][j-1]+f[i+1][j-1];//相当于把数组的线性绕成圈，才能循环传递else if(i==n)f[i][j]=f[1][j-1]+f[i-1][j-1];else f[i][j]=f[i-1][j-1]+f[i+1][j-1];//当前⼈的次数等于上次左边的⼈的次数加右边⼈的次数}cout<<f[1][m];return0;}2.P1541 乌龟棋题⽬背景⼩明过⽣⽇的时候，爸爸送给他⼀副乌龟棋当作礼物。

算法体系类型一、排序算法。

排序算法就像是给一群小朋友排队一样，按照一定的规则把一堆数据排好顺序。

比如说，你有一堆数字，想让它们从小到大或者从大到小排列，这时候就需要排序算法啦。

举例：- 冒泡排序：它就像一群小朋友在比身高，相邻的两个小朋友互相比较，如果左边的比右边的高，那就交换位置，这样一轮一轮比较下去，最高的小朋友就慢慢“冒”到右边去啦。

比如有数字 [3, 1, 4, 2] ，第一轮比较，3和1交换，变成 [1, 3, 4, 2] ，然后3和4不交换，4和2交换，变成 [1, 3, 2, 4] 。

第二轮再继续比较，最后就排好序啦。

- 快速排序：这个算法呢，就像是找一个班长，把同学们分成两拨。

先选一个数字作为“班长”，比它小的放左边，比它大的放右边，然后再对左右两边分别重复这个过程，很快就能排好序啦。

比如对于 [5, 3, 7, 2, 9] ，选5作为“班长”，分成[3, 2] 和 [7, 9] ，再分别对这两组排序。

二、搜索算法。

搜索算法就像是在一个大迷宫里找宝藏，要从很多数据里找到我们想要的那个。

举例：- 线性搜索：这是最简单的一种搜索方法啦，就像你一个一个房间去敲门找宝藏一样。

从第一个数据开始，一个一个比较，看是不是我们要找的那个。

比如在 [2, 4, 6, 8, 10] 里找数字6，就从2开始，依次比较，直到找到6为止。

- 二分搜索：这个就聪明多啦，它先看看中间的那个数是不是宝藏，如果不是，再根据大小判断宝藏在左边还是右边，然后只在那一边继续找。

就像你知道宝藏在房子的左边还是右边，就只在那一边找，效率就高多啦。

比如在 [1, 3, 5, 7, 9] 里找数字5，先看中间的数字3，5比3大，那就只在右边 [5, 7, 9] 里继续找。

三、图算法。

图算法呢，就像是研究地图上各个城市之间的道路关系一样，用来处理图这种数据结构的问题。

举例：- 广度优先搜索（BFS）：想象你在一个城市里，要去各个地方旅游，你先去离你最近的地方，然后再去离这些地方最近的地方，一层一层往外扩展。

动态规划专题分类视图数轴动规题： (1)较复杂的数轴动规 (4)线性动规 (7)区域动规： (14)未知的动规： (20)数轴动规题：题1.2001年普及组第4题--装箱问题【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0<n≤30),每个物品有一个体积（正整数）。

要求从n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

【输入格式】输入文件box.in有若干行。

第一行：一个整数，表示箱子容量V；第二行：一个整数，表示物品个数n；接下来n行，分别表示这n个物品的各自体积。

【输出格式】输出文件box.out只有一行数据，该行只有一个数，表示最小的箱子剩余空间。

【输入样例】2468312797【输出样例】题2.1996年提高组第4题--砝码秤重__数据加强版【问题描述】设有n种砝码,第k种砝码有C k个,每个重量均为W k,求：用这些砝码能秤出的不同重量的个数，但不包括一个砝码也不用的情况。

【输入格式】输入文件weight.in的第一行只有一个数n,表示不同的砝码的种类数.第2行至第n+1行,每行有两个整数.第k+1行的两个数分别表示第k种砝码的个数和重量.【输出格式】输出文件weight.out中只有一行数据:Total=N。

表示用这些砝码能秤出的不同重量数。

【输入样例】22 22 3【输出样例】Total=8【样例说明】重量2,3,4,5,6,7,8,10都能秤得【数据限制】对于100%的数据,砝码的种类n满足:1≤n≤100;对于30%的数据,砝码的总数量C满足:1≤C≤20;对于100%的数据,砝码的总数量C满足:1≤C≤100;对于所有的数据,砝码的总重量W满足:1≤W≤400000;题3.石子归并-szgb.pas【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。

【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。