贪心算法 实验二报告
实验二 贪心选择算法
姓名 : 田圆圆 学号:2013125135
一、实验目的与要求: 理解贪心选择算法的思想。
二、预习与准备:贪心选择算法思想:
(1)贪心选择能得到问题的最优解,要证明我们所做的第一步选择一定包含在一个最优解总,即存在一个最优解的第一步是从我们的贪心选择开始。
(2)在做出第一步贪心选择后剩下的子问题应该是和原问题类似的规模较小的子问题 为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。
三、实验题目:
1.在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短路径。
2.背包问题
给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
3.多机调度问题
要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定,每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理。作业不能拆分成更小的子作业。
四、实验过程:
1.用贪心算法求单元最短路径问题:
其中,dist[i]:表示当前从源到顶点i的最短特殊路径长度。
实验代码为:
#include
#include
#include
using namespace std;
const int V = 9; //定义顶点个数
//从未包含在SPT的集合T中,选取一个到S集合的最短距离的顶点。 int getMinIndex(int dist[V], bool sptSet[V]) {
}
// 打印结果
void printSolution(int dist[], int n) {
}
printf("Vertex Distance from Source\n"); for (int i = 0; i
//source 代表源点
void dijkstra(int graph[V][V], int source) {
//更新到V的距离。可以理解为Bellman-Ford中的松弛操作 for (int v = 0; v
}
} && dist[u] + graph[u][v]
int main() {
}
2.背包问题:
#include return 0; dijkstra(graph, 0); /* 以例子中的图为例 */ int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 0, 10, 0, 2, 0, 0 }, { 0, 0, 0, 14, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
int f[10][100];
//构造最优矩阵
void package0_1(int *w,int *v,int n,int c)
{
int i,j;
//初始化矩阵
for(i=1;i
f[i][0] = 0;
for(j=1;j
f[0][j] = 0;
for(i=1;i
{
for(j=1;j
{
//当容量够放入第i个物品,并且放入之后的价值要比不放大 if(w[i] f[i-1][j])
{
f[i][j] = f[i-1][j-w[i]] + v[i];
}else
f[i][j] = f[i-1][j];
}
}
printf("最大价值: %d \n",f[n][c]);
}
//构造最优解
void getResult(int n,int c,int *res,int *v,int *w)
{
int i,j;
j = c;
for(i=n;i>=1;i--)
{
if(f[i][j] != f[i-1][j])
{
res[i] = 1;
j = j - w[i];
}
}
}
void main()
{
int w[6] = {0,2,2,6,5,4};//每个物品的重量
int v[6] = {0,6,3,5,4,6};//每个物品的价值
int res[5] = {0,0,0,0,0};
int n = 5; //物品的个数
int c = 10; //背包能容的重量
int i,j;
package0_1(w,v,n,c);
for(i=0;i
{
for(j=0;j
printf("%2d ",f[i][j]);
printf("\n");
}
getResult(n,c,res,v,w);
printf("放入背包的物品为: \n");
for(i=1;i
if(res[i] == 1)
printf("%d ",i);
}
3.多机器调配问题:
#include "stdafx.h"
#include "MinHeap.h"
#include
#include
using namespace std;
const int N = 7;//作业个数
const int M = 3;//机器台数
ifstream fin("4d7.txt");
class JobNode
{
//friend void Greedy(JobNode [],int,int);
//friend int main(void);
public:
operator int() const
{
return time;
}
//private:
int ID,time;
};
class MachineNode
{
//friend void Greedy(JobNode [],int,int);
public:
operator int() const
{
return avail;
}
//private:
int ID,avail;
};
template
void Greedy(Type a[],int n,int m);
template
void SelectSort(Type a[],int n);
int main()
{
JobNode a[N+1] ;//各作业所需要的处理时间
cout
for(int i=1; i
{
fin>>a[i].ID>>a[i].time;
coutGreedy(a,N,M);
return 0;
}
template
void Greedy(Type a[],int n,int m)
{
if(n
{
cout
}
SelectSort(a,n);//排序,从大到小
MinHeap H(m);
MachineNode x;
for(int i=1; i
{
x.avail = 0;
x.ID = i;
H.Insert(x);
}
for(int i=1; i
{
x = H.RemoveMin();
coutx.avail += a[i].time;
H.Insert(x);//根据新的avail值将x插入Heap中适当位置 }
}
template
void SelectSort(Type a[],int n)
{
Type temp;
int max;
for(int i=1;i
{
max=i;
for(int j=i+1;j
{
if(a[max]
{
max=j;
}
}
if(max != i)
{
temp = a[i];
a[i] = a[max];
a[max] = temp;
}
}
}
//4d7 贪心算法 多机调度问题
#include "stdafx.h"
#include "MinHeap.h"
#include
#include
using namespace std;
const int N = 7;//作业个数
const int M = 3;//机器台数
ifstream fin("4d7.txt");
class JobNode
{
};
//friend void Greedy(JobNode [],int,int); //friend int main(void); public: operator int() const { } return time; //private: int ID,time;
class MachineNode
{
};
template
void Greedy(Type a[],int n,int m);
template //friend void Greedy(JobNode [],int,int); public: operator int() const { } return avail; //private: int ID,avail;
void SelectSort(Type a[],int n);
int main()
{
}
template
void Greedy(Type a[],int n,int m)
{
if(n H(m); cout>a[i].ID>>a[i].time; cout
}
MachineNode x; for(int i=1; itemplate
void SelectSort(Type a[],int n)
{
Type temp;
int max;
for(int i=1;i
{
max=i;
for(int j=i+1;j
{
if(a[max]
{
max=j;
}
}
if(max != i) { } temp = a[i]; a[i] = a[max]; a[max] = temp;
}
}
五、实验结果与结论:
1.本次实验结果为:
让我对Dijstra算法多了一些认识和体会,它的算法思想是:一个顶点属于S当且仅当源到该顶点的最短路径长度已知。初始S中仅含有源。设u是G的某一顶点,把从源到u且中间只经过S中顶点的录称为从源到u的特殊路径,并用dist数组记录当前每个顶点对应的最短特殊路径长度。
Dijkstra算法每次从V-S中取出具有最短特殊路径长度的顶点u,将u添加到S中,同时对dist数组作必要的修改。一旦S中包含了V中所有顶点,dist就记录了从源到所有其它顶点之间的最短路径长度。
2.0-1背包问题实验结果为:
01背包问题这是一种贪婪的准则为,从剩余的物品中,选出可以装入背包的价值最大的物品,然后是下一个价值最大的物品,如此下去,但不能保证得到最优解。
3.多机器调度问题实验结果为:
六.思考问题:
1、贪心算法与动态规划思想解题的区别?
答:通过做本次试验,我觉得贪心算法与动态规划问题最大的不同就是其解决问题的原理不同,因为贪心算法是只考虑当前问题的最好结果,不管以后怎么样;但是动态规划是一个不断变化的过程,它随着问题的取值不同,不断规划,对所得结果进行比较,最终得到有效的值。
1、哈夫曼编码问题的编程实现?
答:实现哈夫曼算法的大致描述为:
初始化:将2n-1个结点的三个指针域的值置为空(可用-1表 示),权值为0; 输入:读入n个叶结点的权值存入向量的前个分量中,即形成有个结点的森林(一个结点为一棵树);
排序:按权值排序(从小到大)
相关文章
- 贪心算法设计实验报告
- 贪心算法计算最优分解方案
- 哈夫曼编码_贪心算法
- 贪心法求解单元最短路径问题
- 中南大学算法实验报告
- 背包问题贪心算法解决
- 基于微博网络的影响力最大化算法
- 旅行商问题
- 算法设计与分析论文
湖北工业大学计算机学院 <算法设计技巧与分析>课程实验报告 实验名称姓 名 贪心算法的运用 系院专业 指导教师 班 级 实验序号学成 号绩 实验日期一.实验目的 1. 掌握贪心算法的基本概念和两个基本要素2. 熟练掌握贪心算法解 ...
西安邮电大学 (计算机学院) 课内实验报告 实验名称: 专业名称: 班级: 学生姓名: 学号(8指导教师: 实验日期:2016年6月1日 一. 实验目的及实验环境 实验目的: 熟悉并掌握贪心算法 实验环境: windows7 vc6.0编译 ...
淮海工学院计算机工程学院 实验报告书 课程名: <算法分析与设计> 题 目: 实验3 贪心算法 班 级: 软件102班 学 号: 姓 名: 鹿 迅 实验3 贪心算法 实验目的和要求 (1)了解前缀编码的概念,理解数据压缩的基本方 ...
实验1. 贪心法求解单源最短路径问题 实验内容 本实验要求基于算法设计与分析的一般过程(即待求解问题的描述.算法设计.算法描述.算法正确性证明.算法分析.算法实现与测试).应用贪心策略求解有向带权图的单源最短路径问题. 实验目的 通过本次实 ...
算法分析与设计 实验报告 学院: 信息科学与工程学院 专业班级: i got7 指导老师: 学号: i got7 姓名: 鸟宝宝 a. 合并排序 合并排序是分治法的应用,把需要排序的数组A[1 - n],一分为二A[1 -n/2]和A[n/ ...
贪心算法求解背包问题 一. 实验内容 有一个承重为W的背包和n个物品,它们各自的重量和价值分别是wi和vin Wwi求这些物品中最有价值的一个子集.如果每次选择某(1 i1一个物品的时候,只能全部拿走,则这一问题称为离散(0-1)背包 ...
摘 要:由于影响范围的重叠效应,单纯的影响力度量算法并不能解决微博网络中的影响力最大化问题,针对这一研究现状,提出一种用于微博网络中TopK节点挖掘的算法GABE.通过归纳决定微博用户影响力的关键因素,提出了节点间影响率的概念,进而建立了用 ...
1简介 "旅行商问题"常被称为"",是指一名推销员要拜访多个地点时,如何找到在拜访每个地 TSP问题 点一次后再回到起点的最短路径.规则虽然简单,但在地点数目增多后求解却极为复杂.以42个地点为例,如 ...
贪心算法 --不在贪心中爆发,就在贪心中灭亡 武汉理工大学计算机科学与技术学院班 摘要 本文介绍贪心算法的基本意义以及算法的使用范围,并通过具体的案例来分析贪心算法的具体应用,从而指出其特点和存在问题. 关键字:贪心算法,贪心策略,TSP. ...