《贪心算法实验报告》由会员分享，可在线阅读，更多相关《贪心算法实验报告（8页珍藏版）》请在金锄头文库上搜索。
1、福建工程学院计算机与信息科学系实验报告12345篇二：北邮算法作业贪心算法实验报告第三次算法作业（贪心算法）姓名：吴迪班级：08211312学号：08211488班内序号15摘要：本文为完成作业problem1，problem3，problem4，problem5的四道贪心算法题。 备注：所有后缀为_ex的可执行文件为文件输入输出模式的程序，比如problem1_ex.exe （所有算法实现代码承诺为本人自己编写并且截图为实际有效截图，所有程序均通过 dev-c+编译器实际测试可以运行）problem 1特殊的01背包（原算法分析题4-3）问题描述：01背包是在n件物品取出若干件放在空间为c的
2、背包里，每件物品的体积为 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。输入:首先是一个
3、整数t,代表测试数据的组数。每组测试数据首先是两个正整数n和c， n代表物品的个数，c代表背包的最大容积。然后有n行整数，每行有两个整数，分别代表物 品的价值v和体积w。t的范围是（1-100）,n的范围是（1-100000）,c、v、w的范围不超过四字 节的int型。输出：首先输出测试数据的组号，例如第一组的组号为“case 1:”，占一行。然后是一 个整数，代表可以取得的最大价值，占一行。sample input:55 206 201 6020 315 1599 1100 100 5 1092 17101 1093 18109 3 87 26 10 22 96 13 96 18 89 17
4、 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 1094 2153 5695 16 91 20 39 69 82 2854 54110 2 42 67 65 46sample output: case 1: 134case 2: case 3: 109case 4: 212case 5:312问题分析：本题是特殊的01背包问题，由于其价值和重量的反比规律易证明贪婪算法的有效性，故 本题可以采用贪心算法求解，即每次优选最轻物品也是最大价值物品。源代码：(仅附文件输入输出版本，标准输入输出版本见
5、cpp代码文件)#include<iostream>#include<fstream>using namespace std;int greedy_calculate(int* v,int* w,const int n,const int c);int main()/inputintt;/test groupnum 1-100intn;/object num1-100000intc;/capacityint *v;int *w;fstream in;fstream out;in.open(problem1_input.txt,ios:in);out.open(probl
6、em1_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;
7、j<n;j+)in >> vj;in >> wj;/outputout<<case <<i<<:<<endl;out<<greedy_calculate(v,w,n,c)<<endl;/safetydelete 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=
8、-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+)xi=0;while(total_weight<=c&&count<n)least_weight=-1;for(int i=0;i<n;i+)if(xi=0)if(wi<least_weight)least_weight=wi;lw_num=i;xlw_num=1;total_value+=vlw_num;total_weight+=wlw_
9、num;count+;if(total_weight>c)total_value-=vlw_num;total_weight-=wlw_num;delete x;return total_value;运行截图篇三：算法实验报告贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告 篇四：贪心算法解汽车加油问题实验报告一、实验名称：用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。二、实验目的：课程设计是计算机算法与设计课程不可缺少的重要实践性环节。通过实践教学，要 达到以下目的：（1）使学生掌握线性表、栈、队列、串、树
10、、二叉树、图、集合等各种典型抽象数据类 型的数学模型及其所支持基本运算的实现方法；（2）使学生掌握以抽象数据类型为模块的面向对象程序设计方法；（3）使学生提高对实际问题的分析、设计和实现能力；（4）为学生后续课程的学习及课程设计打下坚实的实践基础。三、使用的策略：贪心算法、回溯算法等。四、实验内容：（一）问题描述一辆汽车加满油后可以行驶n千米。旅途中有若干个加油站。指出若要使沿途的加油次 数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出n，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最 少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越
11、快越好。（二）问题分析（前提行驶前车里加满油）对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为ai； i=0，1， 2， 3n1. 始点到终点的距离小于n，则加油次数k=0；2. 始点到终点的距离大于n，a加油站间的距离相等，即a i=aj=l=n，则加油次数最少k=n；b加油站间的距离相等，即ai=aj=l>n，则不可能到达终点；c 加油站间的距离相等，即a i=aj=l<n，则加油次数k=n/n（n%n=0）或 k=n/n+1（n%n! =0）；d加油站间的距离不相等，即ai!=aj，则加油次数k通过以下算法求解。（三）算法描述1. 贪心算法解决方案?贪心算法
12、的基本思想该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的 最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪 心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进 的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在 一定的标准下）。不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选 择产生一个全局得最优解。?贪心算法的适用的问题贪心算法适用的问题必须满足两个属性：（1）贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依 赖以前做出的
13、选择，但不能依赖于以后的选择。（2）最优子结构：问题的整体最优解包含着它的子问题的最优解。?贪心算法的基本步骤(1) 分解：将原问题分解为若干相互独立的阶段。(2) 解决：对于每一个阶段求局部的最优解。(3) 合并：将各个阶段的解合并为原问题的解。问题分析由于汽车是由始向终点方向开的，我们最大的麻烦就是不知道在哪个加油站加油可以使 我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难，取得最优方案。我们可以假设不到万 不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在 局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点
14、，用相同的递归方法进 行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。加油站贪心算法设计(c)：/肖萌的算法 加油站问题贪心算法#include<iostream>using namespace std;int main()int i,j,n,k,l10,c=0,m=0;bool a10;cout<<请输入加满油后可行驶的距离(km)：;cin>>n;cout<<请输入途中所经的加油站个数：；cin>>k;cout<<请输入每相邻两个加油站之间的距离：<<endl;for(i=0;i<=k;i+)cin>>li;for(i=0;i<=k;i+)ai=false;for(j=0;j<=k;j+)m+=lj;if(m+lj+1>=7)aj+1=true;m=0;cout<<在第 ;for(int s=0;s<=k;s+)if(as=true)c+;cout<<s<< ;cout<<个加油站加油了 ！ _<<endl;cout<<最少加油次数为：&l
