福建工程学院计算机与信息科学系
实验报告
1
2
3
4
5 篇二：北邮算法作业贪心算法实验报告
第三次算法作业（贪心算法）
姓名：吴迪
班级学号班内序号 15
摘要：本文为完成作业problem1，problem3，problem4，problem5的四道贪心算法题。
备注：所有后缀为_ex的可执行文件为文件输入输出模式的程序，比如problem1_ex.exe
（所有算法实现代码承诺为本人自己编写并且截图为实际有效截图，所有程序均通过dev-c++编译器实际测试可以运行）
problem 1
特殊的01背包（原算法分析题4-3）
问题描述：01背包是在n件物品取出若干件放在空间为c的背包里，每件物品的体积为w1，w2wn，与之相对应的价值为p1,p2pn，并取得最大价值。普通的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
60
20 3
15 15
99 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
始点到终点的距离小于ｎ，则加油次数k=0；
始点到终点的距离大于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通过以下算法求解。
（三）算法描述
贪心算法解决方案
? 贪心算法的基本思想
该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的最优解
不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪心算法将问
题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解。
? 贪心算法的适用的问题
贪心算法适用的问题必须满足两个属性：
（１） 贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前
做出的选择，但不能依赖于以后的选择。
（２） 最优子结构：问题的整体最优解包含着它的子问题的最优解。
? 贪心算法的基本步骤
（１） 分解：将原问题分解为若干相互独立的阶段。
（２） 解决：对于每一个阶段求局部的最优解。
（３） 合并：将各个阶段的解合并为原问题的解。
[问题分析]
由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。
提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。
加油站贪心算法设计（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千米这段路程上任取两个加油站ａ、ｂ，且ａ距离始点比ｂ距离始点近，则若在ｂ加油不能到达终点那么在ａ加油一定不能到达终点，如图：
由图知：因为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型骨牌不得重叠覆盖。