福建工程学院计算机与信息科学系 实验报告 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.始点到终点的距离小于ｎ，则加油次数k=0； 2.始点到终点的距离大于n， a 加油站间的距离相等，即ａ[i]=a[j]=l=n，则加油次数最少k=n； b 加油站间的距离相等，即ａ[i]=a[j]=l>n，则不可能到达终点； c 加油站间的距离相等，即ａ[i]=a[j]=l<n，则加油次数k=n/n(n%n==0)或
k=[n/n]+1(n%n！=0)；
d 加油站间的距离不相等，即ａ[i]！=a[j]，则加油次数k通过以下算法求解。 （三）算法描述 1.贪心算法解决方案 ? 贪心算法的基本思想 该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的
最优解 不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪
心算法将问 题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选
择产生一个全局得最优解。 ? 贪心算法的适用的问题
贪心算法适用的问题必须满足两个属性： （１） 贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前
做出的选择，但不能依赖于以后的选择。 （２） 最优子结构：问题的整体最优解包含着它的子问题的最优解。
贪心算法实验报告
