当前位置：文档之家 › 动态规划算法设计与应用

动态规划算法设计与应用

  • 格式：doc
  • 大小：85.00 KB
  • 文档页数：10

实验报告

课程 算法设计与分析实验 实验名称 动态规划算法设计与应用 第 1 页

一、实验目的

1.加深对动态规划算法的基本原理的理解，掌握用动态规划方法求解最优化问题的方法步骤及应用；

2.用动态规划设计整数序列的最长递增子序列问题的算法，分析其复杂性，并实现；

3.用动态规划设计求凸多边形的三角剖分问题的算法，分析其复杂性，并实现。

4.选做题：用动态规划设计求解0/1背包问题的算法，分析其复杂性，并实现。

二、实验内容

(一) 最长递增子序列问题

1.问题描述

求一个由n个整数组成的整数序列的最长递增子序列。一个整数序列的递增子序列可以是序列中非连续的数按照原序列顺序排列而成的。 最长递增子序列是其递增子序列中长度最长的。

2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1700题

输入：输入的第一行是一个正整数n，表示测试例个数。接下来几行是n个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数k

(k<=500)，表示整数序列的长度，第二行给出整数序列，整数之间用一个空格隔开。（设给出的每个整数序列的最长递增子序列都是唯一的。）

输出：对于每个测试例输出两行，第一行为最长递增子序列的长度，第二行为最长递增子序列，整数之间用一个空格隔开。两个测试例的输出数据之间用一个空行隔开，最后一个测试例后无空行。

3. 测试数据

输入：3

5

3 1 4 2 3

6

1 3 9 5 2 6

20

1 2 7 13 3 5 10 24 12 4 9 16 53 6 83 8 23 11 31 47

输出：3

1 2 3

4

1 3 5 6

10

1 2 3 5 10 12 16 23 31 47

4. 设计与实现的提示

(1) 寻找最优子结构、写出递归方程是问题的关键。

(2) 以Ai为末元素的最长递增子序列(记为S(i))，等于以使S(j), (j=1～i), 最大的那个Aj为末元素的递增子序列最末再加上Ai；如果这样的元素不存在，那么Ai自身构成一个长度为1的以Ai为末元素的递增子序列。

(3) 最优解的信息在此是以Ai为末元素的最长递增子序列的前驱元素，应当记录下来。

5. 扩展内容

本题可以采用多种方法求解，可以尝试用不同思路求解。

(二) 凸多边形的三角剖分

1. 问题描述

设P是一个有n个顶点的凸多边形，P中的弦是P中连接两个非相邻顶点的线段。用P中的(n-3)条弦将P剖分成(n-2)个三角形（如下图所示）。使得(n-3)条弦的长度之和最小的三角形剖分称为最优三角剖分。

2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1701题

输入：输入的第一行是一个正整数m，表示测试例个数，接下来几行是m个测试例的数据，每个测试例的数据由两行组成，第一行含一个正整数n (n<=500)，表示凸多边形的顶点个数；第二行含2n个实数x1 , y1 , x2 , y2 , „xn , yn ，按顺时针方向依次给出n个顶点的坐标值(xi, yi) i=1, 2, „, n，整数之间用一个空格隔开。

输出：对于每个测试例输出一行，含一个实数（精确到小数点后三位），表示最优三角剖分的n-3条弦的长度之和。两个测试例的输出数据之间用一个空行隔开，最后一个测试例后无空行。

3. 测试数据

输入：

2

6

1 2 2 1.5 2 0.5 1 0 0 0.5 0 1.5

9

723 1220 463 1074 370 842 317 534 524 192 992 87 1378 355 1683 855

1301 1131

输出： 5.606

4928.722

4. 设计与实现的提示

(1) 凸(n+1)边形的最优三角剖分是该凸多边形的所有三角剖分中弦长最短的那个剖分。

(2) 本题与课本7.3节中的矩阵链相乘问题非常相似。寻找最优子结构、写出递归方程是问题的关键，注意递归方程的参数的设置。

(3) 将凸(n+1)边形三角剖分时，注意弦长不要重复计算。

5. 扩展内容

本题只要求计算出最优值。如果要求最优解，在求最优值过程中，要记录下改最优值对应的三角剖分的信息。

(三) 选做题――0/1背包问题

1. 问题描述

设有一个容量为C的背包，n个物品的集合U={u1, u2, „, un}，物品uj的体积和价值分别为sj和vj，C, sj, vj都是正整数。在U中选择物品装入背包，使得装入背包的物品总价值最大。设每种物品或完全装入或完全不装入背包。

2. 具体要求

输入：输入的第一行是一个正整数m，表示测试例个数，接下来几行是m个测试例的数据。每个测试例的数据由三行组成，第一行含两个正整数n和C，其中， n (n<=100)表示给定的是n个物品的集合U={u1, u2, „, un}，C(C<=5000)表示背包的容量；第二行含n个整数s1 , s2 , „sn，表示n个物品的体积；第三行含n个整数v1 , v2 , „vn，表示n个物品的价值，整数之间用一个空格隔开。

输出：对于每个测试例输出2行数据，其中，第一行含一个整数，表示装入背包物品的最大总价值；第2行含n个整数x1 , x2 , „xn，表示u1, u2, „, un

这n个物品是否放入背包。其中xi ={1, 0} , (i=1,2, „,n)。 如果xi =1，表示物品ui放入背包；如果xi =0，表示物品ui不放入背包。每个xi之间用一个空格隔开，两个测试例的输出数据之间用一个空行隔开，最后一个测试例后无空行。

3. 测试数据

输入：2

5 20

7 13 6 4 3

5 7 3 2 3

8 100

7 13 45 25 16 75 48 32

6 5 20 10 7 32 22 13

输出：13

1 0 1 1

48 1 0 1 0 0 0 1 0

4. 设计与实现的提示

(1) 寻找最优子结构、写出递归方程仍是问题求解的关键。

(2) 对于物品是否装入背包，可以有多种表示方式，这里仅采用0，1的方式，即xi=1表示物品ui装入背包；xi=0表示物品ui不装入背包。

(3) 由于在求解最优值时，并非所有的子问题都需要解，因此可以采用自顶向下的递归方法。

(4) 在求解最优值的过程中，注意最优解的相应信息的表示和记录。

5. 扩展内容

(1) 可以练习实现课本第7章的练习7.27可复选的背包问题，并与本题进行比较。

(2) 可以练习实现课本第7章的练习7.26 。

要求：取不同K值，求0/1背包问题的近似最优值，观察分析不同的K值对最优值的精确性的影响。

(3) 可以将本题与一般背包问题（一个物品可以部分装入背包）相比较，可以问题的复杂性和求解方法上有何不同。

三、实验环境

硬件：Windows XP计算机、鼠标、键盘、显示器

开发环境：Microsoft Visual C++ 6.0

四、实验步骤

（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果）

①、 点击开始菜单中的程序-Microsoft Visual C++ 6.0

点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中写入“实验四(1).cpp”,再点击确定.

②、 编写程序如下：

#include

#define MAX 50

/*--------------------------------冒泡排序-----------------------*/

void bubble(int r[],int n,int B[])//使用冒泡排序，将原数组按升序排列

{

int i,j,temp;

for(i=0;i

{

for(j=0;j

if(r[j]>r[j+1])

{

temp=r[j];

r[j]=r[j+1]; r[j+1]=temp;

}

}

for(i=0;i

{

B[i]=r[i];

}

}

/*------------------------求序列A和B的最长公共子序列C-------------------*/

void Lcss(int H[MAX][MAX],int n,int A[MAX],int L,int B[MAX])

{

int i=n,j=n,k=L,C[MAX];

while(i>0&&j>0)

{

if(H[i][j]==0)

{

C[k--]=A[i];

i=i-1;

j=j-1;

}

else

if(H[i][j]==1)

i=i-1;

else

j=j-1;

C[0]=B[0];

}

for(i=0;i

{

printf("%4d",C[i]);

}

}

/*-------求A和B的最长公共子序列长度L[n, m]和存储最长公共子序列的有关信息的数组H[1..n, 1..m]-----*/

void Lcs(int A[MAX],int B[MAX],int n,int num)

{

int i,j,length;

int L[MAX][MAX],H[MAX][MAX];

for(i=0;i

L[i][0]=0;

for(j=0;j

L[0][j]=0;

for(i=1;i<=n;i++)

合集下载

常用算法解析及其应用场景

常用算法解析及其应用场景

常用算法解析及其应用场景

算法是计算机科学中最基础的概念之一。在日常生活中，我们无时无刻不在接触着各种算法，从谷歌搜索到智能手机里各种APP的推荐算法，都离不开算法的支持和应用。在这篇文章中，我将为大家介绍常用的算法和它们的应用场景。

一、排序算法

排序算法是程序中最常用的一种算法，其目的是将数据按一定方式进行排列。常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序和快速排序。

1、冒泡排序

冒泡排序是一种简单的排序算法，它的思路是从头到尾扫描一遍需要排序的数据，每一次将相邻两个元素进行比较并交换位置。这个过程类似于水泡在水中上浮，一遍扫描结束后，最大的元素就会像水泡一样浮到最上面。

冒泡排序的时间复杂度为O(n²)，如果需要排序的数据量很大，那么执行起来会比较慢。不过它的优点在于代码简单易懂，并且实现起来很容易。

2、选择排序

选择排序的思路是每次从数据中选择一个最小（或最大）的元素，并将其放置在序列的起始位置。按照这样的方式，每次只需要找到一个元素，就可以将数据序列排列好。

选择排序的时间复杂度也为O(n²)，但它比冒泡排序要稍微快一点。

3、插入排序

插入排序的思路是将数据分为已排序区间和未排序区间两部分。不断地将未排序区间的元素逐一与已排序区间的元素相比较，找到合适的位置插入。重复执行这个过程，最终就能将整个数据序列排列好。

插入排序的时间复杂度也为O(n²)，但它的执行速度相对于冒泡排序和选择排序要慢一些。不过它的优点在于它在处理小数据量时非常高效，并且在排序过程中需要的额外内存很少。

4、归并排序

归并排序的思路是将数据分成两个子序列，分别进行排序，最后将排序好的子序列进行合并。在合并的过程中，需要使用到一个额外的数组来存储数据。

归并排序的时间复杂度为O(nlogn)，执行效率相对较高。尤其是在处理大数据量时，它表现得十分出色。

5、快速排序

快速排序的思路不同于以上几种排序算法，它是一种分治法的排序算法。快速排序的过程是不断地将数据序列划分为两部分，并递归地对这两个子序列进行排序。

动态规划的基本概念与方法

动态规划的基本概念与方法

动态规划的基本概念与方法

动态规划（Dynamic Programming，简称DP）是解决一类最优化问题的一种方法，也是算法设计中的重要思想。动态规划常用于具有重叠子问题和最优子结构性质的问题。它将问题分解为子问题，并通过求解子问题的最优解来得到原问题的最优解。

动态规划的基本概念是“最优子结构”。也就是说，一个问题的最优解可以由其子问题的最优解推导出来。通过分解问题为若干个子问题，可以形成一个递归的求解过程。为了避免重复计算，动态规划使用一个表格来保存已经计算过的子问题的解，以便后续直接利用。这个表格也被称为“记忆化表”或“DP表”。

动态规划的基本方法是“状态转移”。状态转移指的是，通过已求解的子问题的解推导出更大规模子问题的解。常用的状态转移方程可以通过问题的递推关系定义。通过定义好状态转移方程，可以通过迭代的方式一步步求解问题的最优解。

在动态规划中，通常需要三个步骤来解决问题。

第一步，定义子问题。将原问题划分为若干个子问题。这些子问题通常与原问题具有相同的结构，只是规模更小。例如，对于计算斐波那契数列的问题，可以定义子问题为计算第n个斐波那契数。

第二步，确定状态。状态是求解问题所需要的所有变量的集合。子问题的解需要用到的变量就是状态。也就是说，状态是问题（解决方案）所需要的信息。 第三步，确定状态转移方程。状态转移方程通过已求解的子问题的解推导出更大规模子问题的解。通常情况下，状态转移方程可以通过问题的递推关系确定。

在实际应用中，动态规划常用于求解最优化问题。最优化问题可以归纳为两类：一类是最大化问题，另一类是最小化问题。例如，最长递增子序列问题是一个典型的最大化问题，而背包问题是一个典型的最小化问题。

动态规划的优势在于可以解决许多复杂问题，并且具有可行的计算复杂度。但是，动态规划也有一些限制。首先，动态规划要求问题具有重叠子问题和最优子结构性质，不是所有问题都能够满足这两个条件。其次，动态规划需要存储计算过的子问题的解，对于一些问题来说，存储空间可能会非常大。因此，在使用动态规划求解问题时，需要根据具体情况判断是否适用。

动态规划和贪心算法的时间复杂度分析比较两种算法的效率

动态规划和贪心算法的时间复杂度分析比较两种算法的效率

动态规划和贪心算法的时间复杂度分析比较两种算法的效率

动态规划和贪心算法是常见的算法设计思想，它们在解决问题时具有高效性和灵活性。但是，两者在时间复杂度上有所不同。本文将对动态规划和贪心算法的时间复杂度进行详细分析，并比较这两种算法的效率。

一、动态规划算法的时间复杂度分析

动态规划是一种通过将问题分解成子问题并保存子问题的解来求解的算法。其时间复杂度主要取决于子问题的数量和每个子问题的求解时间。

1. 子问题数量

动态规划算法通常使用一个二维数组来保存子问题的解，数组的大小与原问题规模相关。假设原问题规模为N，每个子问题的规模为k，则子问题数量为N/k。因此，子问题数量与原问题规模N的关系为O(N/k)。

2. 每个子问题的求解时间

每个子问题的求解时间通常也与子问题的规模相关，假设每个子问题的求解时间为T(k)，则整个动态规划算法的时间复杂度可以表示为O(T(k) * N/k)。 综上所述，动态规划算法的时间复杂度可以表示为O(T(k) * N/k)，其中T(k)表示每个子问题的求解时间。

二、贪心算法的时间复杂度分析

贪心算法是一种通过选择当前最优的解来求解问题的算法。其时间复杂度主要取决于问题的规模和每个选择的求解时间。

1. 问题规模

对于贪心算法来说，问题的规模通常是不断缩小的，因此可以假设问题规模为N。

2. 每个选择的求解时间

每个选择的求解时间可以假设为O(1)。贪心算法通常是基于问题的局部最优解进行选择，而不需要计算所有可能的选择。因此，每个选择的求解时间可以认为是常数级别的。

综上所述，贪心算法的时间复杂度可以表示为O(N)。

三、动态规划和贪心算法的效率比较

从时间复杂度的分析结果来看，动态规划算法的时间复杂度为O(T(k) * N/k)，而贪心算法的时间复杂度为O(N)。可以发现，在问题规模较大时，动态规划算法的时间复杂度更高。

原因在于动态规划算法需要保存所有子问题的解，在解决子问题时需要遍历所有可能的选择，因此时间复杂度较高。而贪心算法则不需要保存所有子问题的解，每次选择的求解时间也为常数级别，因此时间复杂度较低。

计算机算法设计五大常用算法的分析及实例

计算机算法设计五大常用算法的分析及实例

计算机算法设计五⼤常⽤算法的分析及实例

摘要

算法（Algorithm）是指解题⽅案的准确⽽完整的描述，是⼀系列解决问题的清晰指令，算法代表着⽤系统的⽅法描述解决问题的策略机制。也就是说，能够对⼀定规范的输⼊，在有限时间内获得所要求的输出。如果⼀个算法有缺陷，或不适合于某个问题，执⾏这个算法将不会解决这个问题。不同的算法可能⽤不同的时间、空间或效率来完成同样的任务。

其中最常见的五中基本算法是递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法。本⽂通过这种算法的分析以及实例的讲解，让读者对算法有更深刻的认识，同时对这五种算法有更清楚认识

关键词：算法，递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法Abstract

Algorithm is the description to the problem solving scheme ,a set of clear instructions to solve the problem and represents thedescribe the strategy to solve the problem using the method of system mechanism . That is to say, given some confirmimport，the Algorithm will find result In a limited time。If an algorithm is defective or is not suitable for a certain job, it isinvalid to execute it. Different algorithms have different need of time or space, and it's efficiency are different.

There are most common algorithms: the recursive and divide and conquer、dynamic programming method、greedyalgorithm、backtracking、branch and bound method.According to analyze the five algorithms and explain examples, makereaders know more about algorithm , and understand the five algorithms more deeply.