当前位置:文档之家› 贪心算法的应用实例

贪心算法的应用实例

贪心算法的应用实例
贪心算法的应用实例

贪心算法经典例题

贪心算法经典例题 发布日期: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

【精选】贪心算法的应用

贪心算法的应用 课程名称:算法设计与分析 院系:计算机科学与信息工程学院 学生姓名:**** 学号:********** 专业班级:********************************** 指导教师:****** 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)

算法设计实验_贪心算法背包问题

《算法分析与设计》 课程实验 专业年级:信息与计算科学 学生学号: 学生姓名: 实验题目:用贪婪法求解背包问题 指导老师: 实验时间:20xx年xx月x日 一、实验内容 用贪婪法求解背包问题 要求:用非递归实现 二、实验步骤 2.1、理解算法思想和问题要求; 2.2、写出每个操作的算法 非递归算法: greedbag() { int N; int c;

int[] w; int[] v; Scanner scan=new Scanner(System.in); System.out.print("输入背包的容量:"); c=scan.nextInt(); System.out.print("输入物品的数量:"); N=scan.nextInt(); System.out.print("分别输入物品的价值:"); v=new int[N]; for(int i=0;i

贪心算法0-1背包问题(算法实验代码)

实验三、0-1背包问题(贪心算法) 实验代码: #include int max(int a,int b) { if(a>b) return a; else return b; } void Knapsack(int *v,int *w,int *x,int c,int n, int m[8][100]) { int i,j; for(j=0;j=1;i--) { for(j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } for(i=1;i

printf("物品总数为:7\n"); printf("物品重量和价值分别为:\n"); printf("\n重量价值\n"); for (i=1;i<=n;i++) printf("%d %d \n",w[i],v[i]); int m=15; int array[8][100]={0}; Knapsack(v,w,x,m,7,array); printf("背包能装的最大价值为: %d\n",array[1][m]); printf("贪心算法的解为: "); for(i=1;i<=n;i++) { if(i==1) printf("%d",x[i]); else printf(" %d",x[i]); } printf("\n"); return 0; } 测试截图为:

实验二 贪心算法的应用

实验二贪心算法的应用 一、实验目的 1.掌握贪心算法的基本概念和两个基本要素 2.熟练掌握贪心算法解决问题的基本步骤。 3.学会利用贪心算法解决实际问题。 二、实验内容 1.问题描述: 题目二:会场安排问题 假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法来进行安排。试编程实现对于给定的k个待安排活动,计算使用的最少会场。输入数据中,第一行是k的值,接下来的k行中,每行有2个正整数,分别表示k个待安排活动的开始时间和结束时间,时间以0点开始的分钟计。输出为最少的会场数。 输入数据示例 5 1 23 12 28 25 35 27 80 36 50 输出数据 3 三、算法分析 Stept1:输入各个活动的开始时间(s)和结束时间(e),初始化各活动的会场号。Step2:按活动的开始时间和活动时间排序,s最早(第一优先级)和持续时间最短(第二优先级)的活动排在最前。 Step3:执行贪婪算法,即s最早和持续时间最短的优先安排会场,并记录会场号,其余活动的s大于或等于已安排活动的e的安排在同一会场,若某活动的s

小于安排活动的e,则安排在另一会场,记录会场号,依次循环,直到所有活动均被安排。 Step4:统计会场号数,输出。 时间复杂度:O(n) 算法时间:O(nlogn) 核心算法: void swap(Active &a,Active&b) { Active t; t=a; a=b; b=t; } //活动时间排序 for(i=1;i<=k;i++) { for(j=i;j<=k;j++) { if(a[i].s>a[j].s) swap(a[i],a[j]); if(a[i].s==a[j].s) { if(a[i].e>a[j].e) swap(a[i],a[j]); } } } 四、程序调试及运行结果分析 五、源代码

C语言版贪心算法背包问题

#include<> #define N 100 typedef struct bao{ int num; float w; float v; }; typedef struct avg{ int num; ( float val; float w; float v; }; struct bao b[N]; struct avg d[N]; int n; float c; ^ void Sort() { int i,j,k; struct avg temp[N]; for(i=0;i

float x[N],sum = 0; for(i=0;ic) break; x[d[i].num] = 1; sum += d[i].v; c -= d[i].w; } if(i

贪心算法解决活动安排问题报告

1.引言: 贪心法是一种改进了的分级处理方法。用贪心法设计算法的特点是一步一步地进行,每一步上都要保证能获得局部最优解。每一步只考虑一个数据,它的选取满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加为止。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心法。 贪心算法总是做出在当前看来是最优的选择,也就是说贪心算法并不是从整体上加以考虑,它所做出的选择只是在某种意义上的局部最优解,而许多问题自身的特性决定了该题运用贪心算法可以得到最优解或较优解。 2.贪心算法的基本思想及存在问题 贪心法的基本思想: 从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解,得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 3.活动安排问题: 3.1 贪心算法解决活动安排问题 学校举办活动的安排问题是用贪心算法有效求解的一个很好例子。活动安排问题要求安排一系列争用某一公共资源的活动。用贪心算法可使尽可能多的活动能兼容的使用公共资源。设有n个活动的集合{0,1,2,…,n-1},其中每个活动都要求使用同一资源,如会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间starti和一个结束时间endi,且starti

贪心算法的应用

从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例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]

背包问题(贪心算法)

算法分析与设计实验报告 第 4 次实验

}

附录:完整代码 #include #include #include struct node{ float value; float weight; }; float Value,curvalue=0; float Weight,curweight=0; //按价重比冒泡排序 void sort(node Node[],int M){ int i,j; node temp; for(i=0;i

贪心算法与动态规划的比较

贪心算法与动态规划的比较 【摘要】介绍了计算机算法设计的两种常用算法思想:贪心算法与动态规划算法。通过介绍两种算法思想的基本原理,比较两种算法的联系和区别。通过背包问题对比了两种算法的使用特点和使用范围。 【关键字】动态规划;贪心算法;背包问题 1、引言 为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展,线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法,你可以使用这些方法来设计算法,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。本文针对部分背包问题和0/ 1 背包问题进行分析,介绍贪心算法和动态规划算法的区别。 2、背包问题的提出 给定n种物品( 每种物品仅有一件) 和一个背包。物品i的重量是w i,其价值为p i,背包的容量为M。问应如何选择物品装入背包,使得装入背包中的物品的总价值最大,每件物品i的装入情况为x i,得到的效益是p i*x i。 ⑴部分背包问题。在选择物品时,可以将物品分割为部分装入背包,即0≤x i≤1 ( 贪心算法)。 ⑵0/ 1背包问题。和部分背包问题相似,但是在选择物品装入时要么不装,要么全装入,即x i = 1或0。( 动态规划算法) 。 3、贪心算法 3.1 贪心算法的基本要素 能够使用贪心算法的许多例子都是最优化问题,每个最优化问题都包含一组限制条件和一个优化函数,符合限制条件的问题求解方案称为可行解;使优化函数取得最佳值的可行解称为最优解。此类所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到(这是贪心算法与动态规划的主要区别) 。 3.2贪心策略的定义 贪心策略是指从问题的初始状态出发,通过若干次的贪心选择而得出最优值( 或较优解) 的一种解题方法。贪心策略总是做出在当前看来是最优的选择,也就是说贪心策略并不是从整体上加以考虑,它所做出的选择只是在某种意义上的局部最优解,而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。(注:贪心算法不是对所有问题都能

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

武汉理工大学 算法设计与分析论文题目:贪心算法应用研究 姓名:吴兵 学院:信息工程 专业班级:电子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)

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

贪心算法背包问题

算法设计与分析实验报告 题目:贪心算法背包问题 专业:JA V A技术xx——xxx班 学号: 姓名: 指导老师:

实验三:贪心算法背包问题 一、实验目的与要求 1、掌握背包问题的算法 2、初步掌握贪心算法 二、实验题: 问题描述:与0-1背包问题相似,给定n种物品和一个背包。物品i的重量是wi,其价值为vi,背包的容量为c。与0-1背包问题不同的是,在选择物品i装入背包时,背包问题的解决可以选择物品i的一部分,而不一定要全部装入背包,1< i < n。 三、实验代码 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class er extends JFrame { private static final long serialVersionUID = -1508220487443708466L; private static final int width = 360;// 面板的宽度 private static final int height = 300;// 面板的高度 public int M; public int[] w; public int[] p; public int length; er() { // 初始Frame参数设置 this.setTitle("贪心算法"); setDefaultCloseOperation(EXIT_ON_CLOSE); setSize(width, height); Container c = getContentPane(); c.setLayout(new BoxLayout(c, BoxLayout.Y_AXIS)); setLocation(350, 150); // 声明一些字体样式 Font topF1 = new Font("宋体", Font.BOLD, 28); Font black15 = new Font("宋体", Font.PLAIN, 20); Font bold10 = new Font("宋体", Font.BOLD, 15); // 声明工具栏及属性设置 JPanel barPanel = new JPanel(); JMenuBar topBar = new JMenuBar(); topBar.setLocation(1, 1); barPanel.add(topBar); // 面板1和顶部标签属性设置 JPanel p1 = new JPanel(); JLabel topLabel = new JLabel("背包问题");

贪心算法的应用实例

贪心算法的应用实例 例2.排队问题 【题目描述】 在一个医院B 超室,有n个人要做不同身体部位的B超,已知每个人需要处理的时间为ti,(00,从而新的序列比原最优序列好,这与假设矛盾,故s1为最小时间,同理可证s2…sn依次最小。 例3.:数列极差问题 【题目描述】 在黑板上写了N个正整数做成的一个数列,进行如下操作:每一次擦去其中的两个数a 和b,然后在数列中加入一个数a×b+1,如此下去直至黑板上剩下一个数,在所有按这种操作方式最后得到的数中,最大的max,最小的为min,则该数列的极差定义为M=max-min。 编程任务:对于给定的数列,编程计算出极差M。 输入输出样例: 输入: 4 2 1 4 3 输出: 13 【算法分析】 当看到此题时,我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开,着重探讨求max的问题。 下面我们以求max为例来讨论此题用贪心策略求解的合理性。 讨论:假设经(N-3)次变换后得到3个数:a ,b , max'(max'≥a≥b),其中max'是(N-2)个数经(N-3)次f变换后所得的最大值,此时有两种求值方式,设其所求值分别为 z1,z2,则有:z1=(a×b+1)×max'+1,z2=(a×max'+1)×b+1所以z1-z2=max'-b≥0若经(N-2)次变换后所得的3个数为:m,a,

c应用贪心算法求解背包问题

实验五应用贪心算法求解背包问题 学院:计算机科学与技术专业:计算机科学与技术 学号:班级:姓名: 、 实验内容: 背包问题指的是:有一个承重为W的背包和n个物品,它们各自的重量和价值分别是n ,假设W w i和v i(1 i n)w i 1i,求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候,只能全部拿走,则这一问题称为离散(0-1)背包问题;如果每次可以拿走某一物品的任意一部分,则这一问题称为连续背包问题。 二、算法思想: 首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。 三、实验过程: #in elude using n amespace std; struct goodi nfo

{ float p; // 物品效益 float w; // 物品重量 float X; // 物品该放的数量 int flag; // 物品编号 };// 物品信息结构体 void Insertionsort(goodinfo goods[],int n)// 插入排序,按pi/wi 价值收益进行排序,一般教材上按冒泡排序 { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].p>goods[i].p) { } goods[i+1]=goods[0]; } }// 按物品效益,重量比值做升序排列goods[i+1]=goods[i]; i--; void bag(goodinfo goods[],float M,int n) { float cu; int i,j;

贪心算法详解分析

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

数据结构课设_TSP贪心算法

数据结构课程设计 设计说明书 题目 TSP问题贪心算法 起止日期:2014年11月10 日至2014 年11月17日 计算机科学与工程学院 2014年11月9日

课程设计任务书 一、设计目的 熟悉各种数据结构和运算,会使用数据结构的基本操作解决一些实际问题。二、设计要求 在本课程设计过程中要求学生: (1)重视课程设计环节,用严谨、科学和踏实的工作态度对待课程设计的每一项任务; (2)按照课程设计的题目要求,独立地完成各项任务,严禁抄袭;凡发现抄袭,抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同,涉及的全部人员皆以零分计入本课程设计成绩。 (3)学生在接受设计任务后,根据要求认真完成。 (4)认真编写课程设计报告。 三、设计内容 TSP问题(贪心法求解) 1) 问题描述 所谓TSP问题是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次,并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题,是图问题中最广为人知的问题。 2) 基本要求 (1) 上网查找TSP问题的应用实例; (2) 分析求TSP问题的全局最优解的时间复杂度; (3) 设计一个求近似解的算法; (4) 分析算法的时间复杂度。 3) 设计思想 对于TSP问题,一种最容易想到的也肯定能得到最佳解的算法是穷举法,即考虑所有可能的旅行路线,从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为Ο(n!),当n大到一定程度后是不可解的。

4)设计思想 对于TSP问题,一种最容易想到的也肯定能得到最佳解的算法是穷举法,即考虑所有可能的旅行路线,从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为Ο(n!),当n 大到一定程度后是不可解的。 本实验只要求近似解,可以采用贪心法求解:任意选择某个城市作为出发点,然后前往最近的未访问的城市,直到所有的城市都被访问并且仅被访问一次,最后返回到出发点。 为便于查找离某顶点最近的邻接点,可以采用邻接矩阵存储该图。算法用伪代码描述如下: 1. 任意选择某个顶点v作为出发点; 2. 执行下述过程,直到所有顶点都被访问: 2.1 v=最后一个被访问的顶点; 2.2 在顶点v的邻接点中查找距离顶点v最近的未被访问的邻接点j; 2.2 访问顶点j; 3. 从最后一个访问的顶点直接回到出发点v; 四、参考文献 1. 王红梅,数据结构,清华大学出版社; 2. 王红梅,数据结构学习辅导与实验指导,清华大学出版社; 3. 王晓东,计算机算法设计与分析,电子工业出版社。

贪心算法实现背包问题算法设计与分析实验报告

算法设计与分析实验报告 实验名称贪心算法实现背包问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1. 优化问题 有n个输入,而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成,而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解,称为最优解。 2.贪心法求优化问题 算法思想:在贪心算法中采用逐步构造最优解的方法。在每个阶段,都作出一个看上去最优的决策(在一定的标准下)。决策一旦作出,就不可再更改。作出贪心决策的依据称为贪心准则(greedy criterion)。 3.一般方法 1)根据题意,选取一种量度标准。 2)按这种量度标准对这n个输入排序 3)依次选择输入量加入部分解中。如果当前这个输入量的加入,不满足约束条件,则不把此输入加到这部分解中。 procedure GREEDY(A,n) /*贪心法一般控制流程*/ //A(1:n)包含n个输入// solutions←φ //将解向量solution初始化为空/ for i←1 to n do x←SELECT(A) if FEASIBLE(solution,x) then solutions←UNION(solution,x) endif repeat return(solution) end GREEDY 4. 实现典型的贪心算法的编程与上机实验,验证算法的时间复杂性函数。 二.实验内容 1. 编程实现背包问题贪心算法。通过具体算法理解如何通过局部最优实现全局最优,

并验证算法的时间复杂性。 2.输入5个的图的邻接矩阵,程序加入统计prim算法访问图的节点数和边数的语句。 3.将统计数与复杂性函数所计算比较次数比较,用表格列出比较结果,给出文字分析。 三.程序算法 1.背包问题的贪心算法 procedure KNAPSACK(P,W,M,X,n) //P(1:n)和W(1;n)分别含有按 P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值 和重量。M是背包的容量大小,而x(1:n)是解向量 real P(1:n),W(1:n),X(1:n),M,cu; integer i,n; X←0 //将解向量初始化为零 cu←M //cu是背包剩余容量 for i←1 to n do if W(i)>cu then exit endif X(i) ←1 cu←cu-W(i) repeat if i≤n then X(i) ←cu/ W(i) endif end GREEDY-KNAPSACK procedure prim(G,) status←“unseen” // T为空 status[1]←“tree node” // 将1放入T for each edge(1,w) do status[w]←“fringe” // 找到T的邻接点 dad[w] ←1; //w通过1与T建立联系 dist[w] ←weight(1,w) //w到T的距离 repeat while status[t]≠“tree node” do pick a fringe u with min dist[w] // 选取到T最近的节点 status[u]←“tree node” for each edge(u,w) do 修改w和T的关系 repeat repeat 2.Prim算法

贪心算法设计与应用

实验报告 课程算法设计与分析实验实验名称贪心算法设计与应用第 1 页一、实验目的 理解贪心算法的基本原理,掌握贪心算法设计的基本方法及其应用; 二、实验内容 (一)Huffman编码和译码问题: 1.问题描述 给定n个字符在文件中的出现频率,利用Huffman树进行Huffman编码和译码。设计一个程序实现: 1.输入含n(n<=10)个字符的字符集S以及S中各个字符在文件中的出现频 率,建立相应的Huffman树,求出S中各个字符的Huffman编码。 2.输入一个由S中的字符组成的序列L,求L的Huffman 编码。 3. 输入一个二进制位串B,对B进行Huffman译码,输出对应的字符序列; 若不能译码,则输出无解信息。 提示:对应10 个字符的Huffman树的节点个数<211。 2.测试数据 Input n=5 字符集合S={a, b, c, d, e}, 对应的频率分别为 a: 20 b: 7 c: 10 d: 4 e: 18 字符序列L=ebcca 二进制位串B=01100111010010 Output S中各个字符的Huffman编码:(设Huffman树中左孩子的权<=右孩子的权)a: 11 b: 010 c: 00 d: 011 e: 10 L的Huffman 编码:10010000011 B对应的字符序列: dcaeeb 若输入的B=01111101001,则无解 (二) 加油问题(Problem Set 1702): 1.问题描述 一个旅行家想驾驶汽车从城市A到城市B(设出发时油箱是空的)。给定两个

城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=1,2,…,n。设d[1]=0=xw和yb>=yw。 若黑点b支配白点w,则黑点b和白点w可匹配(可形成一个匹配对)。在一

贪心算法实现01背包问题

贪心算法实现01背包问题 算法思想:贪心原则为单位价值最大且重量最小,不超过背包最大承重量为约束条件。也就是说,存在单位重量价值相等的两个包,则选取重量较小的那个背包。 具体实现过程是:首先可以设置一个备份pvu类型的数组,在不破环原数据的情况下,对此备份数组按单位重量价值从大到小的排序。依次设立两个指针i,j(其中i表示当前应该参与最佳pv值的元素指针,j表示符合约束条件的指针(单位重量价值PV最大,重量最小,不超过最大承重量约束) 代码实现如下: #include using namespace std; typedef struct { int v; int w; float pv; }pvu; void sortByPv(pvu [],int ); int zeroneBags(pvu[],int,int,int * ); void print(pvu a[],int n) { for (int i=0;i

相关主题
文本预览
相关文档 最新文档