文档库 最新最全的文档下载
当前位置:文档库 › 贪心算法实验报告

贪心算法实验报告

贪心算法实验报告
贪心算法实验报告

福建工程学院计算机与信息科学系

实验报告

1

2

3

4

5

篇二:北邮算法作业贪心算法实验报告

第三次算法作业(贪心算法)

姓名:吴迪

班级:08211312

学号:08211488

班内序号 15 摘要:本文为完成作业problem1,problem3,problem4,problem5的四道贪心算法题。

备注:所有后缀为_ex的可执行文件为文件输入输出模式的程序,比如problem1_ex.exe (所有算法实现代码承诺为本人自己编写并且截图为实际有效截图,所有程序均通过

dev-c++编译器实际测试可以运行)

problem 1 特殊的01背包(原算法分析题4-3)

问题描述:01背包是在n件物品取出若干件放在空间为c的背包里,每件物品的体积为

w1,w2??wn,与之相对应的价值为p1,p2??pn,并取得最大价值。普通的01背包中物品的重

量和价值没有明确的关系,这里定义一种特殊的01背包:向背包中放入的物品的价值和体积

成反比,也就是价值越高,体积越小,注意这里物品价值和体积的乘积并不是固定值。例如:

如下的物品满足这

个“特殊的01背包”,5件物品: 物品1,价值 v=6,体积w=20 物品2,价值 v=1,体积w=60 物品3,价值 v=20,体积w=3 物品4,价值 v=15,体积w=15 物品5,价值 v=99,体积w=1 假如我有一个容量为c的背包,c=20,那么选择物品3、4、5可以获得最大价值134。

输入:首先是一个整数t,代表测试数据的组数。每组测试数据首先是两个正整数n和c,

n代表物品的个数,c代表背包的最大容积。然后有n行整数,每行有两个整数,分别代表物

品的价值v和体积w。t的范围是(1-100),n的范围是(1-100000),c、v、w的范围不超过四字

节的int型。

输出:首先输出测试数据的组号,例如第一组的组号为“case 1:”,占一行。然后是一

个整数,代表可以取得的最大价值,占一行。

sample input:

5

5 20

6 20

1 60

20 3

15 15

99 1 1 1

100 100 5 10

92 17

101 10

93 18

109 3

87 26 10 22

96 13

96 18

89 17

106 1

71 40

86 27

83 31

78 31

106 7 68 46 15 19

54 55

103 7

82 33

75 35

99 10

94 21

53 56

95 16

91 20

39 69

82 28

54 54

110 2

42 67

65 46 sample output:

case 1:

134

case 2: case 3:

109

case 4:

212

case 5:

312 问题分析:

本题是特殊的01背包问题,由于其价值和重量的反比规律易证明贪婪算法的有效性,故

本题可以采用贪心算法求解,即每次优选最轻物品也是最大价值物品。

源代码:(仅附文件输入输出版本,标准输入输出版本见cpp代码文件)

#include<iostream>

#include<fstream>

using namespace std;

int greedy_calculate(int* v,int* w,const int n,const int c); int main()

{

//input int t; //test group num 1-100 int n; //object num 1-100000 int c; //capacity

int *v;

int *w;

fstream in;

fstream out;

in.open(problem1_input.txt,ios::in); out.open(problem1_output.txt,ios::out); in >> t; if(t>100||t<1)

out<<error input of t!<<endl; for(int i=0;i<t;i++){

in >> n;

if(n>100000||n<1)

out<<error input of n!<<endl; in >> c; if(c<=0)

out<<error input of c!<<endl; v=new int [n]; w=new int [n];

for(int j=0;j<n;j++)

{

in >> v[j];

in >> w[j];

} //output

out<<case <<i<<:<<endl; out<<greedy_calculate(v,w,n,c)<<endl; //safety

delete v;

delete w;

}

in.close();

out.close();

system(pause);

return 0;

}

int greedy_calculate(int* v,int* w,const int n,const int c) { unsigned int least_weight=-1; int lw_num=0; int count=0;

int total_value=0;

int total_weight=0;

bool *x;

x=new bool [n];

for(int i=0;i<n;i++)

{

x[i]=0;

}

while(total_weight<=c&&count<n){ least_weight=-1;

for(int i=0;i<n;i++)

{

if(x[i]==0){

if(w[i]<least_weight)

{

least_weight=w[i];

lw_num=i; } }

}

x[lw_num]=1;

total_value+=v[lw_num];

total_weight+=w[lw_num];

count++;

}

if(total_weight>c)

{

total_value-=v[lw_num];

total_weight-=w[lw_num]; } delete x;

return total_value;

}

运行截图篇三:算法实验报告

贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告

贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告

篇四:贪心算法解汽车加油问题实验报告

一、实验名称:

用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。

二、实验目的:

课程设计是《计算机算法与设计》课程不可缺少的重要实践性环节。通过实践教学,要达到以下目的:

(1)使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现方法;

(2)使学生掌握以抽象数据类型为模块的面向对象程序设计方法;

(3)使学生提高对实际问题的分析、设计和实现能力;

(4)为学生后续课程的学习及课程设计打下坚实的实践基础。

三、使用的策略:

贪心算法、回溯算法等。

四、实验内容:

(一)问题描述

一辆汽车加满油后可以行驶n千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。

给出n,并以数组的形式给出加油站的个数及相邻距离,指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。要求:算法执行的速度越快越好。

(二)问题分析(前提行驶前车里加满油)

对于这个问题我们有以下几种情况:设加油次数为k,每个加油站间距离为a[i];i=0,1,2,3……n

1.始点到终点的距离小于n,则加油次数k=0;

2.始点到终点的距离大于n,

a 加油站间的距离相等,即a[i]=a[j]=l=n,则加油次数最少k=n;

b 加油站间的距离相等,即a[i]=a[j]=l>n,则不可能到达终点;

c 加油站间的距离相等,即a[i]=a[j]=l<n,则加油次数k=n/n(n%n==0)或k=[n/n]+1(n%n!=0);

d 加油站间的距离不相等,即a[i]!=a[j],则加油次数k通过以下算法求解。

(三)算法描述

1.贪心算法解决方案

? 贪心算法的基本思想

该题目求加油最少次数,即求最优解的问题,可分成几个步骤,一般来说,每个步骤的最优解

不一定是整个问题的最优解,然而对于有些问题,局部贪心可以得到全局的最优解。贪心算法将问

题的求解过程看作是一系列选择,从问题的某一个初始解出发,向给定目标推进。推进的每一阶段不是依据某一个固定的递推式,而是在每一个阶段都看上去是一个最优的决策(在一定的标准下)。不断地将问题实例归纳为更小的相似的子问题,并期望做出的局部最优的选择产生一个全局得最优解。

? 贪心算法的适用的问题

贪心算法适用的问题必须满足两个属性:

(1)贪心性质:整体的最优解可通过一系列局部最优解达到,并且每次的选择可以依赖以前

做出的选择,但不能依赖于以后的选择。

(2)最优子结构:问题的整体最优解包含着它的子问题的最优解。

? 贪心算法的基本步骤

(1)分解:将原问题分解为若干相互独立的阶段。

(2)解决:对于每一个阶段求局部的最优解。

(3)合并:将各个阶段的解合并为原问题的解。

[问题分析] 由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使

我们既可以到达终点又可以使我们加油次数最少。

提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万

不得已我们不加油,即除非我们油箱里的油不足以开到下一个加油站,我们才加一次油。在

局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点,用相同的递归方法进

行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。

加油站贪心算法设计(c):

//肖萌的算法加油站问题贪心算法

#include<iostream>

using namespace std;

int main()

{

int i,j,n,k,l[10],c=0,m=0; bool a[10];

cout<<请输入加满油后可行驶的距离(km): ; cin>>n;

cout<<请输入途中所经的加油站个数: ; cin>>k;

cout<<请输入每相邻两个加油站之间的距离: <<endl; for(i=0;i<=k;i++)

cin>>l[i];

for(i=0;i<=k;i++)

a[i]=false;

for(j=0;j<=k;j++)

{

m+=l[j];

if(m+l[j+1]>=7)

{

a[j+1]=true; m=0;

}

}

cout<<在第 ;

for(int s=0;s<=k;s++)

if(a[s]==true)

{

c++;

cout<<s<< ;

}

cout<<个加油站加油了! ^_^<<endl; cout<<最少加油次数为: <<c<<endl; return 0; }贪心算法正确性证明:

? 贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心

选择来达到。对于一个具体的问题,要确定它是否具有贪心性质,我们必须证明每一步所作

的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的n千米这段路程上

任取两个加油站a、b,且a距离始点比b距离始点近,则若在b加油不能到达终点那么在

a加油一定不能到达终点,如图:

由图知:因为m+n<n+n,即在b点加油可行驶的路程比在a点加油可行驶的路程要长

n-m千米,所以只要终点不在b、c之间且在c的右边的话,根据贪心选择,为使加油次数最

少就会选择距离加满油得点远一些的加油站去加油,因此,加油次数最少满足贪心选择性质。

? 最优子结构性质:

当一个问题大的最优解包含着它的子问题的最优解时,称该问题具有最优子结构性质。

由于(b[1],b[2],……b[n])是这段路程加油次数最少的一个满足贪心选择性质的最优解,

则易知若在第一个加油站加油时,b[1]=1,则(b[2],b[3],……b[n])是从 a[2]到a[n]这段

路程上加油次数最少且这段路程上的加油站个数为(a[2],a[3],……a[n])的最优解,即每次

汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油,每个过程从加

油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件,每个过程都

是相同且独立,也就是说加油次数最少具有最优子结构性质。

贪心算法时间复杂度分析

由于若想知道该在哪个加油站加油就必须遍历所有的加油站,且不需要重复遍历,所以

时间复杂度为o(n)。

}

(四)贪心算法、动态规划与回溯算法比较

首先通过以上分析及证明,我们知道两种方法都能解决使汽车加油次数最少的问题。从

证明算法的正确性上回溯算法要更简单,但从时间复杂度上分析贪心算法要更优于回溯算法

在计算机上更容易实现,动态规划介于两者之间,并不是本题最优的选择方案。

五、实验心得:

在贪心算法中,每次做出的选择仅在当前的状态下做出的最好的选择,即局部最优选择。

然后再去解做出这个选择后产生的相应的子问题。不是每个问题用贪心算法都可以一定得到

最优解,除非该问题具有贪心选择性质(所求问题的整体最优解可以通过一系列局部最优的

选择而得到)和最优子结构性质。

在回溯算法中,我们学会了从多角度分析一个问题,通过解空间深度遍历来解决问题,

得到最优解。在回溯算法我们想到可以通过使每次加油前汽车内剩下的油量之和最小的思路,

我们又想到了动态规划算法,动态规划法也可以解决最优解问题,所以我们又分析得出了动

态规划的算法程序。

计算机算法与设计分析

班级:

姓名:

学号:

目录

实验一分治与递归 ?????????????????????????????1

1、基本递归算法??????????????????????????????1

2、棋盘覆盖问题??????????????????????????????2

3、二分搜索????????????????????????????????3

4、实验小结????????????????????????????????5 实验二动态规划算

法 ???? ???????????????????????5

1、最长公共子序列问题 ??????????????????????????5

2、最大子段和问题?????????????????????????????7

3、实验小结????????????????????????????????8 实验三贪心算

法?? ????????????????????????????8

1、多机调度问题??????????????????????????????8

2、用贪心算法求解最小生成树????????????????????????10

3、实验小结????????????????????????????????12 实验四回溯算法和分支限界法????????????????????????12

1、符号三角形问题?????????????????????????????12

2、0—1背包问题??????????????????????????????14

3、实验小结 ????????????????????????????????18

实验一分治与递归(4学时)

一、实验目的与要求

1、熟悉c/c++语言的集成开发环境;

2、通过本实验加深对递归过程的理解

二、实验内容:

掌握递归算法的概念和基本思想,分析并掌握“整数划分”问题的递归算法。

三、实验题

任意输入一个整数,输出结果能够用递归方法实现整数的划分。

#include <iostream>

using namespace std;

int main()

{ int a,b,c; int q(int n,int m); cout<<请输入整数及大于最大加数的数

<<endl;

cin>>a>>b;

c=q(a,b);

cout<<所需要的划分数为:<<c<<endl; return 0;

}

int q(int n,int m) { } if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n<m)

return q(n,n); if (n==m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m);

实验结果:

结果分析:

实验时入得数据为:所要划分的整数是7,他的划分的最大加数的值不得大于7,根据实

际其划分的情况为15种,因而可知其程序的运行结果是正确的。

1

一、实验目的与要求

1、掌握棋盘覆盖问题的算法;

2、初步掌握分治算法

二、实验题:

盘覆盖问题:在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称

该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同

形态的l型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个l型骨牌不

得重叠覆盖。

算法设计与分析实验报告贪心算法

算法设计与分析实验报告 贪心算法 班级:2013156 学号:201315614 姓名:张春阳哈夫曼编码 代码 #include float small1,small2; int flag1,flag2,count; typedefstructHuffmanTree { float weight; intlchild,rchild,parent; }huffman; huffmanhuffmantree[100]; void CreatHuffmanTree(intn,int m) { inti; void select(); printf("请输入%d个节点的权值:",n); for(i=0;i

printf("\n"); for(i=0;i

贪心算法经典例题

贪心算法经典例题 发布日期:2009-1-8 浏览次数:1180 本资料需要注册并登录后才能下载! ·用户名密码验证码找回密码·您还未注册?请注册 您的账户余额为元,余额已不足,请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。 从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌(NOIP2002tg) [问题描述] 有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。例如 N=4,4 堆纸牌数分别为: ①9 ②8 ③17 ④ 6 移动3次可达到目的: 从③取 4 张牌放到④(9 8 13 10) -> 从③取 3 张牌放到②(9 11 10 10)-> 从②取 1 张牌放到①(10 10 10 10)。 [输入]:键盘输入文件名。 文件格式:N(N 堆纸牌,1 <= N <= 100) A1 A2 … An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) [输出]:输出至屏幕。格式为:所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in: 4 9 8 17 6 屏慕显示:3 算法分析:设a[i]为第i堆纸牌的张数(0<=i<=n),v为均分后每堆纸牌的张数,s为最小移到次数。 我们用贪心法,按照从左到右的顺序移动纸牌。如第i堆(0

北京理工大学《数据结构与算法设计》实验报告实验一

《数据结构与算法设计》 实验报告 ——实验一 学院: 班级: 学号: 姓名:

一、实验目的 1.通过实验实践、巩固线性表的相关操作; 2.熟悉VC环境,加强编程、调试的练习; 3.用C语言编写函数,实现循环链表的建立、插入、删除、取数据等基本操作; 4.理论知识与实际问题相结合,利用上述基本操作实现约瑟夫环。 二、实验内容 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现: ①从键盘输入整数m,通过create函数生成一个具有m个结点的单向环表。环表中的 结点编号依次为1,2,……,m。 ②从键盘输入整数s(1<=s<=m)和n,从环表的第s个结点开始计数为1,当计数到 第n个结点时,输出该第n结点对应的编号,将该结点从环表中消除,从输出结点 的下一个结点开始重新计数到n,这样,不断进行计数,不断进行输出,直到输出 了这个环表的全部结点为止。 三、程序设计 1、概要设计 为实现上述程序功能,应用单向环表寄存编号,为此需要建立一个抽象数据类型:单向环表。 (1)、单向环表的抽象数据类型定义为: ADT Joseph{ 数据对象:D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系:R1={ |ai∈D,i=1,2,……,n} 基本操作: create(&L,n) 操作结果:构造一个有n个结点的单向环表L。 show(L) 初始条件:单向环表L已存在。 操作结果:按顺序在屏幕上输出L的数据元素。 Josephf( L,m,s,n) 初始条件:单向环表L已存在, s>0,n>0,s

算法习题

算法设计与分析试卷 一、填空题(20分,每空2分) 1、算法的性质包括输入、输出、确定性、有限性。 2、动态规划算法的基本思想就将待求问题分解成若干个子问题、先求解子问题,然后 从这些子问题的解得到原问题的解。 3、设计动态规划算法的4个步骤: (1)找出最优解的性质,并刻画其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值得到的信息,构造最优解。 4、流水作业调度问题的johnson算法: (1)令N1={i|ai=bj}; (2)将N1中作业依ai的ai的非减序排序;将N2中作业依bi的非增序排序。 5、对于流水作业高度问题,必存在一个最优调度π,使得作业π(i)和π(i+1)满足Johnson不等式min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}。 6、最优二叉搜索树即是最小平均查找长度的二叉搜索树。 二、综合题(50分) 1、当(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时,最大子段和为∑ak(2<=k<=4)=20(5分) 2、由流水作业调度问题的最优子结构性质可知,T(N,0)=min{ai+T(N-{i},bi)}(1=sum){ sum=thissum; besti=i; bestj=j;} } return sum; } 4、设计最优二叉搜索树问题的动态规划算法OptimalBinarysearchTree? (15分) Void OptimalBinarysearchTree(int a,int n,int * * m, int * * w) { for(int i=0;i<=n;i++) {w[i+1][i]=a[i]; m[i+1][i]= 0;} for(int r=0;r

算法设计与分析实验报告

本科实验报告 课程名称:算法设计与分析 实验项目:递归与分治算法 实验地点:计算机系实验楼110 专业班级:物联网1601 学号:2016002105 学生姓名:俞梦真 指导教师:郝晓丽

2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1.进一步熟悉C/C++语言的集成开发环境; 2.通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治(Divide-and-Conquer)的思想:一个规模为n的复杂问题的求解,可以划分成若干个规模小于n的子问题,再将子问题的解合并成原问题的解。 需要注意的是,分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同,可用相同的求解方法。最后,当子问题规模足够小时,可以直接求解,然后逆求原问题的解。 1.4 实验题目 1.上机题目:格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素,每个元素都是长度为n的串,相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码(分治、减治、变治皆可)。 对于给定的正整数n,格雷码为满足如下条件的一个编码序列。 (1)序列由2n个编码组成,每个编码都是长度为n的二进制位串。 (2)序列中无相同的编码。 (3)序列中位置相邻的两个编码恰有一位不同。 2.设计思想:

根据格雷码的性质,找到他的规律,可发现,1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0,N-2为倒转再前面再加1。 3.代码设计:

算法设计与实验报告讲解

算法设计与分析实验报告 学院:信息学院 专业:物联网1101 姓名:黄振亮 学号:20113379 2013年11月

目录 作业1 0-1背包问题的动态规划算法 (7) 1.1算法应用背景 (3) 1.2算法原理 (3) 1.3算法描述 (4) 1.4程序实现及程序截图 (4) 1.4.1程序源码 (4) 1.4.2程序截图 (5) 1.5学习或程序调试心得 (6) 作业2 0-1背包问题的回溯算法 (7) 2.1算法应用背景 (3) 2.2算法原理 (3) 2.3算法描述 (4) 2.4程序实现及程序截图 (4) 2.4.1程序源码 (4) 2.4.2程序截图 (5) 2.5学习或程序调试心得 (6) 作业3循环赛日程表的分治算法 (7) 3.1算法应用背景 (3) 3.2算法原理 (3) 3.3算法描述 (4) 3.4程序实现及程序截图 (4)

3.4.1程序源码 (4) 3.4.2程序截图 (5) 3.5学习或程序调试心得 (6) 作业4活动安排的贪心算法 (7) 4.1算法应用背景 (3) 4.2算法原理 (3) 4.3算法描述 (4) 4.4程序实现及程序截图 (4) 4.4.1程序源码 (4) 4.4.2程序截图 (5) 4.5学习或程序调试心得 (6)

作业1 0-1背包问题的动态规划算法 1.1算法应用背景 从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值,在上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。 1.2算法原理 1.2.1、问题描述: 给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问:应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 形式化描述:给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi ∈{0,1}, ?∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 1.2.2、最优性原理: 设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有 ∑vizi > ∑viyi (i=2,…,n) 且 w1y1+ ∑wizi<= c 因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n) 说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。 1.2.3、递推关系:

贪心算法概论

贪心算法概论 贪心算法一般来说是解决“最优问题”,具有编程简单、运行效率高、空间 复杂度低等特点。是信息学竞赛中的一个有为武器,受到广大同学们的青睐。本 讲就贪心算法的特点作些概念上的总结。 一、贪心算法与简单枚举和动态规划的运行方式比较 贪心算法一般是求“最优解”这类问题的。最优解问题可描述为:有n个输入,它的解是由这n 个输入的某个子集组成,并且这个子集必须满足事先给定的条 件。这个条件称为约束条件。而把满足约束条件的子集称为该问题的可行解。这 些可行解可能有多个。为了衡量可行解的优劣,事先给了一个关于可行解的函数,称为目标函数。目标函数最大(或最小)的可行解,称为最优解。 a)求“最优解”最原始的方法为搜索枚举方案法(一般为回溯法)。 除了极简单的问题,一般用深度优先搜索或宽度优先搜索。通常优化方法为利用约束条件进行可行性判断剪枝;或利用目标函数下界(或上界),根据当前最 优解进行分枝定界。 b)其次现今竞赛中用的比较普遍的动态规划(需要满足阶段无后效性原则)。 动态规划主要是利用最最优子问题的确定性,从后向前(即从小规模向大规模)得到当前最优策略,从而避免了重复的搜索。 举例说明:求多段图的最短路径。

在图(1)中,我们省略了各线段的长度。 如果用回溯法,搜索树大致如下: 显然,上面的搜索有大量重复性工作。比如节点8、9、10到11的最短路分别被调用了9次,从节点5、6、7到节点11也分别搜索了3次。 如果先算出节点8、9、10到11的最短路,由于它与前面的点无关,因此最优值确定下来,再用它们求定节点5、6、7 到节点11 的最短路径。同理,再用节 点5、6、7 的最优值,来求节点2、3、4 优值。最后从节点2、3、4 推出1 到 11的最优值。显然复杂度大为降低。 当然,如果本题把简单搜索改为搜索+记忆化的方法,则就是得能动态规划的原理,本质上就是动态规划,只是实现的方法不同与传统的表格操作法。搜索+记忆化算法有其特有的特点,以后再讨论。 c)贪心算法则不同,它不是建立在枚举方案的基础上的。它从前向后,根据当前情况,“贪心地”决定出下一步,从而一步一步直接走下去,最终得到解。 假如上面的例子中,我们定下这样的贪心策略:节点号k%3= =1。则有图3:

【精选】贪心算法的应用

贪心算法的应用 课程名称:算法设计与分析 院系:计算机科学与信息工程学院 学生姓名:**** 学号:********** 专业班级:********************************** 指导教师:****** 201312-27

贪心算法的应用 摘要:顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质:贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择,即贪心选择达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题是一个经典的问题,我们可以采用多种算法去求解0/1背包问题,比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。 关键词:贪心法背包问题最优化

目录 第1章绪论 (3) 1.1 贪心算法的背景知识 (3) 1.2 贪心算法的前景意义 (3) 第2章贪心算法的理论知识 (4) 2.1 问题的模式 (4) 2.2 贪心算法的一般性描述 (4) 第3章背包问题 (5) 3.1 问题描述 (5) 3.2 问题分析 (5) 3.3算法设计 (5) 3.4 测试结果与分析 (10) 第4章结论 (12) 参考文献 (13) 附件 (13)

银行家算法设计实验报告

银行家算法设计实验报告

银行家算法设计实验报告 一.题目分析 1.银行家算法: 我们可以把操作系统看做是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程尚需求的资源量,若是系统现存的资源可以满足它尚需求的资源量,则按当前的申请量来分配资源,否则就推迟分配。 当进程在执行中继续申请资源时,先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配,若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量,若满足即可按当前的申请量来分配,若不满足亦推迟分配。 2.基本要求: (1)可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项,以及T0时刻系统的可利用资源数。 (2)对T0时刻的进行安全性检测,即检测在T0时刻该状态是否安全。

(3)进程申请资源,用银行家算法对其进行检测,分为以下三种情况: A. 所申请的资源大于其所需资源,提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源, 但大于系统此时的可利用资源,提 示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源, 亦未大于系统此时的可利用资源,预 分配并进行安全性检查: a. 预分配后系统是安全的,将该进 程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态,提示系统不安全并返回。 (4)对输入进行检查,即若输入不符合条件,应当报错并返回重新输入。 3.目的: 根据设计题目的要求,充分地分析和理解题 目,叙述系统的要求,明确程序要求实现的功能以及限制条件。 明白自己需要用代码实现的功能,清楚编写每部分代码的目的,做到有的放矢,有条理不遗漏的用代码实现银行家算法。

算法分析与设计期末模拟试题

安徽大学2010-2011学年第1学期《算法分析与设计》 期末试题 押宝 (内部交流,非考试试题,学生自发交流创作,版权归作者testfudan@https://www.wendangku.net/doc/6a17304250.html, 所有) 一、选择题(单选)(10*2’=20’) 1. 选择正确的组合对于 2112n +=( ) ①2()o n ② 2()O n ③2()n θ ④2()n Ω ⑤ 2()n ω A. ①③④ B. ②③④ C.③④⑤ D. ①⑤ 2. ①21()()n i i O n O n ==∑ ②2()()n O n O n = ③(log )()O n O n ? ④ 2.99993 ()n O n = ⑤2/lo g ()n n n ω=其中正确的有( ) A .5组 B.4组 C.3组 D.没有正确的 3. 2/102n n +=( ) A. 2()O n B.(2)n O C.2(2)n n O + D.2 ()o n 4. 211/n += ( )(我认为是比较不错的一道题,考试可能会出现相同的方法,用极限定义来做,最后一节课老师也讲过类似的方法) A. ()O n B.()o n C.()n Ω D.(1)O 5. 310lo g n = ( ) A.(log )O n n B. (log )O n C. 3()O n D. lo g ()n O n 6. 认真完成课后习题P5面的算法分析题1-6,里面也有我不会做的,可是有谁愿意讨论? 如果能够把以上的题目都能做对,应该就是掌握了。给自己一个奖励吧!答案(如有问题,联系我吧):1-5:BBBDB 6.做出来对对答案吧。 二、填空题 1.()2(/2)T n T n n =+????的一个渐进上界为 (答案:(log )O n n ,用迭代法) 2.()(/3)(2/3)()T n T n T n O n =++的一个渐进上界为 (答案:(log )O n n ,用递归树求解,不会的赶快看) 3.()9(/3)T n T n n =+的一个渐进紧致界为 (答案:2 ()n θ,采用迭代法或者采用主方法,不会的赶快看)

贪心算法详解分析

贪心算法详解 贪心算法思想: 顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。 贪心算法的基本要素: 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路: 从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时,算法停止。 该算法存在问题: 1. 不能保证求得的最后解是最佳的; 2. 不能用来求最大或最小解问题; 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程: 从问题的某一初始解出发; while 能朝给定总目标前进一步do 求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解; 用背包问题来介绍贪心算法: 背包问题:有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大,但不能超过总容量。

南京邮电大学算法设计实验报告——动态规划法

实验报告 (2009/2010学年第一学期) 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程

实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的:加深对动态规划法的算法原理及实现过程的理解,学习用动态规划法解决实际应用中的最长公共子序列问题。 任务:用动态规划法实现求两序列的最长公共子序列,其比较结果可用于基因比较、文章比较等多个领域。 要求:掌握动态规划法的思想,及动态规划法在实际中的应用;分析最长公共子序列的问题特征,选择算法策略并设计具体算法,编程实现两输入序列的比较,并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件:计算机 软件:Visual C++

三、实验原理及内容(包括操作过程、结果分析等) 1、最长公共子序列(LCS)问题是:给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n},要求找出X和Y的一个最长公共子序列。 例如:X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列,检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法,求解时间为指数级别的,因此不可取。 2、分析LCS问题特征可知,如果Z={z1,z2,……,z k}为它们的最长公共子序列,则它们一定具有以下性质: (1)若x m=y n,则z k=x m=y n,且Z k-1是X m-1和Y n-1的最长公共子序列; (2)若x m≠y n且x m≠z k,则Z是X m-1和Y的最长公共子序列; (3)若x m≠y n且z k≠y n,则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题,分解为求解较小规模的问题: 若x m=y m,则进一步分解为求解两个(前缀)子字符序列X m-1和Y n-1的最长公共子序列问题; 如果x m≠y n,则原问题转化为求解两个子问题,即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列,取两者中较长者作为X和Y的最长公共子序列。 由此可见,两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列,具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度,由上述分析可得如下递推式: 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见,最长公共子序列的求解具有重叠子问题性质,如果采用递归算法实现,会得到一个指数时间算法,因此需要采用动态规划法自底向上求解,并保存子问题的解,这样可以避免重复计算子问题,在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解(即最长公共子序列),还需要一个二维数组s[][],数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到,从而可以得到最优解的当前解分量(即最长公共子序列中的当前字符),最终构造出最长公共子序列自身。

贪心算法的应用

从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌(NOIP2002tg) [问题描述] 有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。例如 N=4,4 堆纸牌数分别为: ①9 ②8 ③17 ④6 移动3次可达到目的: 从③取 4 张牌放到④(9 8 13 10) -> 从③取 3 张牌放到②(9 11 10 10)-> 从②取 1 张牌放到①(10 10 10 10)。 [输入]:键盘输入文件名。 文件格式:N(N 堆纸牌,1 <= N <= 100) A1 A2 … An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) [输出]:输出至屏幕。格式为:所有堆均达到相等时的最少移动次数。 [输入输出样例] : 4 9 8 17 6 屏慕显示:3 算法分析:设a[i]为第i堆纸牌的张数(0<=i<=n),v为均分后每堆纸牌的张数,s为最小移到次数。 我们用贪心法,按照从左到右的顺序移动纸牌。如第i堆(0v,则将a[i]-v张纸牌从第I堆移动到第I+1堆; (2)若a[i]

贪心算法解汽车加油问题实验报告

计算机算法与分析 设计报告 班级:信管一班信管二班 姓名(学号):赵立贺(060340219) 赵艳(060340114)刘辉(060340125)王勇(060340116)万玉琪(060340213)刘旺(060340205)指导教师:赵晓峰姚天祥 设计地点:信息系统实验室 信息管理系 2008年12月13日

一、实验名称: 用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。 二、实验目的: 课程设计是《计算机算法与设计》课程不可缺少的重要实践性环节。通过实践教学,要达到以下目的: (1)使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现方法; (2)使学生掌握以抽象数据类型为模块的面向对象程序设计方法; (3)使学生提高对实际问题的分析、设计和实现能力; (4)为学生后续课程的学习及课程设计打下坚实的实践基础。 三、使用的策略: 贪心算法、回溯算法等。 四、实验内容: (一)问题描述 一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。 给出N,并以数组的形式给出加油站的个数及相邻距离,指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。要求:算法执行的速度越快越好。 (二)问题分析(前提行驶前车里加满油) 对于这个问题我们有以下几种情况:设加油次数为k,每个加油站间距离为a[i];i=0,1,2,3……n 1.始点到终点的距离小于N,则加油次数k=0; 2.始点到终点的距离大于N, A 加油站间的距离相等,即a[i]=a[j]=L=N,则加油次数最少k=n; B 加油站间的距离相等,即a[i]=a[j]=L>N,则不可能到达终点; C 加油站间的距离相等,即a[i]=a[j]=L

算法与设计实验报告

算法与分析实验报告软件工程专业 安徽工业大学 指导老师:许精明

实验内容 1:杨辉三角 2:背包问题 3:汉诺塔问题 一:实验目的 1:掌握动态规划算法的基本思想,学会用其解决实际问题。 2:通过几个基本的实验,提高算法分析与设计能力,提高动手操作能力和培养良好的编程习惯。 二:实验内容 1:杨辉三角 2:背包问题 3:汉诺塔问题 实验一:杨辉三角

问题分析: ①每行数字左右对称,由1开始逐渐变大,然后变小,回到1。 ②第n行数之和为2^n。 ③下一行每个数字等于上一行的左右两个数字之和。 算法设计及相关源代码: public void yanghui(int n) { int[] a = new int[n]; if(n==1){ System.out.println(1); }else if(n==2) { System.out.print(1 + " " +1); }else{ a[1]=1; System.out.println(a[1]); a[2]=1;

System.out.println(a[1]+" "+a[2]); for(int i=3;i<=n;i++){ a[1]=a[i]=1; for(int j=i-1;j>1;j--){ a[j]=a[j]+a[j-1]; } for(int j=1;j<=i;j++){ System.out.print(a[j]+" "); } System.out.println(); } } } 实验结果:n=10 实验二:0-1背包问题 问题分析::令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就 j(1<=j<=C)的背包中的物品的最大价值,则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) j

贪心算法经典问题:活动安排,背包问题,最优装载,单源最短路径 Dijiksra,找零钱问题,多机调度

活动安排 public static int greedySelector(int [] s, int [] f, boolean a[]) { //s[]开始时间f[]结束时间 int n=s.length-1; a[1]=true; int j=1; int count=1; for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { a[i]=true; j=i; count++; } else a[i]=false; } return count; } 背包问题 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); //以每种物品单位重量的价值Vi/Wi从大到小排序 int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) { if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; //允许放入一个物品的一部分 } 最优装载 void Loading(int x[], T ype w[], T ype c, int n) { int *t = new int [n+1]; //t[i]要存的是w[j]中重量从小到大的数组下标Sort(w, t, n); //按货箱重量排序 for (int i = 1; i <= n; i++) x[i] = 0; //O(n) for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]];} //调整剩余空间 } 单源最短路径Dijiksra template void Dijikstra(int n, int v, Type dist[], int prev[], Type **c) { //c[i][j]表示边(i,j)的权,dist[i]表示当前从源到顶点i的最短特殊路径bool s[maxint]; for(int i= 1;i<=n; i++) { dist[i]=c[v][i]; s[i]=false;

计算机算法与分析贪心算法实验报告

实验03 贪心算法 一、实验目的 1.掌握贪心算法的基本思想 2.掌握贪心算法中贪心选择性质和最优子结构性质的分析与证明 3.掌握贪心算法求解问题的方法 二、实验内容 1.认真阅读算法设计教材,了解贪心算法思想及方法; 2.设计用贪心算法求解最优装载哈夫曼编码、单源最短路径、最小生成树的 java程序 三、求解的问题 1.哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中 各个字符出现的频率,求各个字符的哈夫曼编码方案。 2.给定带权有向图G =(V,E),其中每条边的权是非负实数。另外,还给定V 中的一个顶点,称为源。现在要计算从源到所有其他各顶点的最短路长度。 这里路的长度是指路上各边权之和。 3.设G =(V,E)是无向连通带权图,即一个网络。E中每条边(v,w)的权为 c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中,耗费最小的生成树称为G的最小生成树。求G的最小生成树。 四、实验程序 1.哈夫曼编码 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始,执行|C|-1次的“合并”运算后产生最终所要求的树T。下面所给出的算法huffmanTree中,编码字符集中的每一字符c的频率是f(c)。以f 为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的两棵具有最小频率的树。一旦两棵具有最小频率的树合并后,产生一棵新的树,其频率为合并两棵树的频率之和,并将新树插入优先队列Q。 private static class Huffman implements Comparable{ Bintree tree; float weight; private Huffman(Bintree tt,float ww) { tree=tt;weight=ww; } public int compareTo(Object x){ float xw=((Huffman) x).weight; if(weight

算法设计实验报告(川大陈瑜)

《算法设计》课程报告 课序号: 01 学号: 2012141461134 姓名:刘佳玉 任课教师:陈瑜 评阅成绩: 评阅意见: 提交报告时间:2014年 6 月 16 日

贪心算法 1、问题描述 (这是我在soj上找的一道题,以前没做出来,现在用贪心的思想做出来了) 约翰要去钓鱼。他有h小时可用(1≤h≤16),在这个地区有n个湖泊(2≤n≤25),所有的湖泊沿着一条单行道可到达。约翰从湖泊1开始,他可以在任何湖泊结束。他只能从一个湖,到下一个,但他没有必要停在任何湖除非他想停。对于每个i = 1,……,n-1,ti 表示从湖i到湖i+1的5分钟的时间间隔(0 < ti < = 192)。例如,t3 = 4意味着它从湖3湖4需要20分钟的时间。 为了帮助他们规划自己的钓鱼旅行,约翰已经收集了一些关于湖泊信息。对于每个湖泊的i,能钓到的鱼在最初的5分钟的数量,用fi表示(fi > = 0),是已知的。每钓5分钟的鱼,能钓到的鱼在接下来的5分钟的间隔降低一个恒定的数di(di>=0)。如果能钓到的鱼在一个时间区的数量小于或等于di,将不会有更多的鱼留在湖里在下一个时间间隔。为了简化规划,约翰认为没有人会在影响他期待钓到的鱼的数量的湖里钓鱼。 写一个程序来帮助约翰计划他的最大化期望钓到的鱼的数量的钓鱼之旅。在每个湖花费的时间数必须是5的倍数。 这个问题包含多个测试案例! 一个多输入的第一行是一个整数N,然后一个空白行后的N个输入块。每个输入块由问题描述中的格式表示的。每个输入块之间有一个空行。 输出格式包含N个输出块。输出块之间要有一个空白行。 输入 在输入中,会给你一个案例输入的数量。每一种情况下,以n开始,其次是h,接下来有一行n个整数指定fi(1 < =i< = n),然后有一行n个整数di(1≤i<=n),最后,有一行n - 1的整数ti(1≤i<=n-1)。输入在n=0的情况下终止。 输出

算法分析与设计选修课-贪心算法应用研究

武汉理工大学 算法设计与分析论文题目:贪心算法应用研究 姓名:吴兵 学院:信息工程 专业班级:电子133 学号: 1409721303131 任课教师:张小梅

目录 摘要 (1) 1.绪论 (2) 2贪心算法的基本知识概述 (3) 2.1 贪心算法定义 (3) 2.2 贪心算法的基本思路及实现过程 (3) 2.3贪心算法的核心 (3) 2.4贪心算法的基本要素 (4) 2.5 贪心算法的理论基础 (6) 2.6 贪心算法存在的问题 (7) 3贪心算法经典应用举例 (8) 3.1删数问题 (8) 3.2 汽车加油问题 (10) 3.3会场安排问题 (12) 4.总结 (16) 5.参考文献 (17)

摘要 在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择,但决不依赖于将来的选择,也不依赖于子问题的解,因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决,贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程,贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题,对于实际应用中的问题,也希望通过贪心算法的特点来解决。 关键词:贪心算法最小生成树多处最优服务次序问题删数问题

《算法设计与分析》实验报告

算法设计与分析课程实验项目目录 学生:学号: *实验项目类型:演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。

本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日~6月30日温度24℃ 1.实验目的和要求: 熟悉蛮力法的设计思想。 2.实验原理和主要容: 实验原理:蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容:以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序,实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的: S END +MORE MONEY . 这里有两个前提假设: 第一,字母和十进制数字之间一一对应,也就是每个字母只代表一个数字,而且不同的字母代表不同的数字;第二,数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意,解可能并不是唯一的,不同人的解可能并不相同。3.实验结果及分析: (将程序和实验结果粘贴,程序能够注释清楚更好。)

该算法程序代码如下: #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数:\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l

相关文档