实验二 贪心选择算法
姓名 ： 田圆圆 学号：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个叶结点的权值存入向量的前个分量中，即形成有个结点的森林（一个结点为一棵树）；
排序：按权值排序（从小到大）
实验二 贪心选择算法
姓名 ： 田圆圆 学号：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个叶结点的权值存入向量的前个分量中，即形成有个结点的森林（一个结点为一棵树）；
排序：按权值排序（从小到大）