学 号 09710118
《算法设计与分析》
实验报告四
电子与信息工程系
2012 年 4 月 6 日
实验四：贪心算法运用练习
一、实验目的
本次实验是针对贪心算法的设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。
二、实验步骤与要求
1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；
2．学生独自完成实验指定内容；
3．实验结束后，用统一的实验报告模板编写实验报告。
4．提交说明：
（1）电子版提交说明：
a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验四_学号_姓名”，
如“《算法设计与分析》实验四_09290101_张三”。
b 压缩包内为一个“《算法设计与分析》实验四_学号_姓名”命名的顶层文件夹，
其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验
报告电子版”。其下分别放置对应实验成果物。
（2）打印版提交说明：
a 不可随意更改模板样式。
b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号
字。
c 行间距：单倍行距。
（3）提交截止时间：20##年4月20日16:00。
三、实验项目
请从下列题目列表中任选2道或3道题目，运用贪心算法对问题的进行求解。
备选题目列表如下：
1．教材第106页所记述的0-1背包问题。
2．教材课后习题4-9；
3．教材课后习题4-21。
四、实验过程
（一）题目一：给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包的容量为c。问如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
1. 题目分析
给定c>0;wi>0;vo>0,1≤i≤n,要求找出一个n元0-1向量（x1,x2,……xn）,xi∈{0,1},1≤i≤n,使得∑wixi≤c,而且∑vixi达到最大。
2. 算法构造
首先计算每种物品单位重量的价值vi.wi；然后，依贪心算法策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全装入背包后，背包内的物品总重量为超过c，则选择单位质量价值次高的物品并尽可能多地装入背包。
3. 算法实现
// tanxin.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
//使用冒泡排序对v[]/w[]单位价值的物品进行从大到小的排序
void Sort(int n,float v[],float w[]){
float t1,t2;
for(int i=0;i<n;i++)
for(int j=0;j<n-i-1;j++)
{
float a=v[i]/w[i]; //比较变量
float b=v[i+1]/w[i+1];
if (a<b)
{//交换
t1=v[i]; v[i]=v[i+1]; v[i+1]=t1;
t2=w[i]; w[i]=w[i+1]; w[i+1]=t2;
}
}
}
//贪心算法主要步骤
void Knapsack(int n,float M,float v[],float w[],float x[]){
Sort(n,v,w); //对要放入的物品进行排序
int i;
for (i=0;i<n;i++) //首先对放入的数组置空，以便分辨是否放入
{
x[i]=0;
}
float c=M; //剩余容量，且用于比较容量
for (i=0;i<n;i++)
{
if (w[i]>c) break; //质量大于容量的不予考虑
x[i]=1;
c-=w[i]; //物品放入，剩余容量减少
}
if (i<=n)
{
x[i]=c/w[i]; //未放满时，部分放入
}
}
//输出放入的情况x[]表示物品放入的单位质量或单位价值
void Print(int n,float v[],float w[],float x[]){
int i;
for(i=0;i<n;i++){
if(x[i]!=0)
cout<<"第"<<i+1<<"物品放入质量为："<<(x[i]*w[i])<<"价值是："<<(x[i]*v[i])<<endl;
}
}
int main(){
int n;
float M=50.0;
cout<<"物品的种类"<<endl;
cin>>n;
cout<<"背包的容量为："<<M<<endl;
//定义动态数组
float *v=new float[n];
float *w=new float[n];
float *x=new float[n];
cout<<"输入物品的价值："<<endl;
for (int i=0;i<n;i++)
{
cin>>v[i];
}
cout<<"输入物品的质量："<<endl;
for(int i=0;i<n;i++){
cin>>w[i];
}
Knapsack(n,M,v,w,x);
Print(n,v,w,x);
system("pause");
return 0;
}
4. 运行结果
5. 经验归纳
这次题比较简单，相比于动态规划，贪心算法要好理解的多。主要是分几个步骤，排序，装入，和部分装入。此次题目的重点不在于排序上面，故我选择的比较简单的冒泡排序。
（二）题目二：汽车加油问题，一辆汽车加满油后可行驶n km。旅途中有若干加油站。设计一个有效算法指出应在哪些加油站停靠加油。使沿途加油次数最少。并证明算法能产生一个最优解。
1. 题目分析
对于给定n和k个加油站位置，a[i]记录i站到i+1站的距离。使用贪心算法计算最少加油次数。
2. 算法构造
记录每站走过的路程，在a[i]在满油能跑完的情况下，进行记录。若每走一段还能继续跑，则往下一站走，若达不到下一站，则在这一站加油。
3. 算法实现
// bus.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;
int main(){
int n,k;
bool isSolution=true;
int m=0,count=0;
ofstream infile("input.txt");
cout<<"enter n and k:"<<endl;
cin>>n>>k;
infile<<n<<k<<endl;//从文件中输出汽车加满油后可行驶距离n，加油站的个数k
int *a = new int [k+1];
for(int i = 0;i <= k;i++) //输入各加油站的间距
{
cin>>a[i];
infile<<a[i]<<" ";
}
infile<<endl;
int *b = new int [k+1];
b[0] = 0;
int j=0;
while(j <= k)
{
if(a[j]>n) //如果成立，油用完的时候达不到下一个加油站。则不能到达目的地
{
isSolution = false;
break; //跳出循环
}
count += a[j]; //记录走的路程
if(count > n)
{
b[j] = j; //记录最优解
count = 0;
m++; //m记录最少的加油次数
}
else //继续走想下一个加油站
{
j += 1;
b[j] = 0;
}
}
infile.close();
ofstream outfile("output.txt");
if(isSolution) //将结果写入文件
{
outfile<<"最少加油次数是："<<m<<endl; //写入文件
//cout<<"最少加油次数是："<<m<<endl; 显示器验证一下是否正确
}
else
cout<<"No Solution";
for (int i = 1;i <= k;i++)
{
if(b[i]!= 0){
outfile<<"第"<<b[i]<<"站加油 "; //自己添加的第i站加油
// cout<<"第"<<b[i]<<"站加油 ";
}
}
cout<<endl;
outfile.close();
system("pause");
return 0;
}
4. 运行结果
5. 经验归纳
此次实验理解清楚了就好做了，只是第一次使用文件，故而有些生疏。翻开了以前的书重新学习一遍文件的使用。经过多次试验，终于完成了。对于题目的要求，本人加了在哪一站加油的。以验证自己的正确性。
五、实验总结
此次实验比较简单主要考察了贪心算法的实践，由于算法思路简单。故而易实现，不过在文件使用上不太了解，重新翻阅以前的书籍，才得以重新掌握。本来想把第三个问题也做的，但是，经过多次努力，无法想出怎样贪心，查阅了资料书，上面只给出一句话，没有理解其中意思。希望老师能够讲解其中的算法。下次会继续努力。
第二篇：《算法设计与分析》实验报告实验二
武 汉 工 程 大 学
计算机科学与工程学院
《算法设计与分析》实验报告
