《算法设计与分析-贪心法》上机实验报告
gin-top: 0px; margin-bottom: 0px; -ms-text-justify: inter-ideograph;">54. return 0;
55. }
四、运行输出结果：
1、 背包问题--1262
2、 最小生成树----1036
3、 最小生成树----1191
4、 单源最短路径问题----1077
五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：
1、首先是背包问题，我一开始搞错了，以为重量是不可分的，后来发现我理解错了，浪费了很多时间
2、其次是这个最小生成树的问题，尤其是1911，报错runtime error，我一直找不到错误，现在看来应该是连通性判断的问题，介于时间所限，我换了种方式进行实现，在这我将原先的代码放在这里。
1. #include <iostream>
2. #include <algorithm>
3. #include <cmath>
4. #include <cstring>
5. using namespace std;
6.
7. int arc[501][501]={0};
8. int city[101];
9.
10. typedef struct{
11. int lowcost; //邻接点的权值
12. int adjvex; //下一邻接点
13. }Element;
14.
15. int Prim(int w, int n){
16. int i,j,k;
17. int min;
18. int length = 0;
19. Element shortEdge[501];
20. for(i=0; i<n; ++i){
21. shortEdge[i].lowcost = arc[w][i];
22. shortEdge[i].adjvex = w;
23. }
24. shortEdge[w].lowcost = 0;
25. for(i=0; i<n-1; ++i){
26. min = 9999;
27. for(j=0; j<n; ++j){
28. if((shortEdge[j].lowcost != -1)&&(shortEdge[j].lowcost < min)){
29. min = shortEdge[j].lowcost;
30. k = j;
31. }
32. }
33. // cout<<shortEdge[k].adjvex<<"--"<<k<<endl;
34. // cout<<shortEdge[k].adjvex<<" "<<k<<" "<<arc[shortEdge[k].adjvex][k]<<endl;
35. if(arc[shortEdge[k].adjvex][k]!=-1)
36. length += arc[shortEdge[k].adjvex][k];
37. shortEdge[k].lowcost = 0;
38. for(j=0; j<n; ++j){
39. if(arc[k][j] < shortEdge[j].lowcost){
40. shortEdge[j].lowcost = arc[k][j];
41. shortEdge[j].adjvex = k;
42. }
43. }
44. }
45. return length;
46. }
47.
48. int main()
49. {
50. int num_example;
51. cin>>num_example;
52. while(num_example--){
53. int n,m,k; //n存活城市数量 m路的数量 k连接的城市数
54. cin>>n>>m>>k;
55.
56. memset(arc,9999,sizeof(arc));
57.
58. for(int i=0; i<m; ++i){
59. int mi, mj, v;
60. cin>>mi>>mj>>v;
61. arc[mi-1][mj-1] = arc[mj-1][mi-1] = v;
62. arc[i][i] = -1;
63. }
64. for(int i=0; i<k; ++i){
65. int citieNum;
66. cin>>citieNum;
67. for(int j=0; j<citieNum; ++j)
68. cin>>city[j];
69. for(int j=0; j<citieNum-1; ++j)
70. for(int k=j+1; k<citieNum; ++k){
71. arc[city[j]-1][city[k]-1] = arc[city[k]-1][city[j]-1] = 0;
72. }
73. }
74. cout<<Prim(0,n);
75. }
76. }
, 一、实验内容：
贪心法问题。
二、所用算法的基本思想及复杂度分析：
1、 背包问题--1262
1） 基本思想
首先按照单位重量价值对重量和价值数组进行降序排序，然后从大到小依次装入背包直到装不下为止。
2） 复杂度分析
T(n)=O(n)。
2、 最小生成树----1036
1） 基本思想
选定一个顶点，然后找最短边，然后对这个最短边的邻接点找最短边，如此反复，直到所有点都已经加入。
2） 复杂度分析
最大的有两层for循环，复杂度都是O(n)，所以总的就是T(n)=O(n2)。
3、 最小生成树----1191
1） 基本思想
和2类似，只不过将未输入的路径记为无穷，输入的路径存入arc矩阵，之后就是一个求最小生成树的过程。
2） 复杂度分析
同2
4、 单源最短路径问题----1077
1） 基本思想
用dijkstra算法，找从n到i的每一个最短路径，最终算得从n到0的最短路径。因为要从n到i到0，那么n到i必然是最短路径。
2） 复杂度分析
一层while和一层for循环，T(n)=O(n2)。
三、源程序及注释：
1、 背包问题--1262
2、 #include <iostream>
3、 #include <algorithm>
4、 #include <cmath>
5、 using namespace std;
6、
7、 struct Goods{
8、 int id;
9、
10、 int w=0;
11、 int v=0;
12、 double v_perw=0;
13、 int num=0;
14、 };
15、
16、
17、
18、 bool cmp(Goods good1, Goods good2){
19、 return good1.v_perw > good2.v_perw;
20、 }
21、
22、 bool cmp_id(Goods good1, Goods good2){
23、 return good1.id < good2.id;
24、 }
25、
26、 double KnapSack(Goods good[], int n, int c){
27、 double maxValue = 0;
28、 sort(good,good+n,cmp);
29、 for(int i=0; i<n; ++i){
30、 if(c>=good[i].w){
31、 maxValue += good[i].v;
32、 c -= good[i].w;
33、 good[i].num = good[i].w;
34、 }else{
35、 maxValue += c*good[i].v_perw;
36、 good[i].num = c;
37、 break;
38、 }
39、 }
40、 return maxValue;
41、 }
42、
43、 int main(){
44、 //w重量 v价值 n物品数 c背包容量
45、 Goods good[1000];
46、 int n,c;
47、 cin>>n>>c;
48、 for(int i=0; i<n; ++i){
49、 cin>>good[i].w>>good[i].v;
50、 good[i].v_perw = 1.0*good[i].v/good[i].w;
51、 good[i].id = i;
52、 }
53、 printf("%.2lf\n",KnapSack(good,n,c));
54、 sort(good,good+n,cmp_id);
55、 for(int i=0; i<n-1; ++i){
56、 cout<<good[i].num<<" ";
57、 }
58、 cout<<good[n-1].num;
59、 }
60、 最小生成树----1036
61、 #include <iostream>
62、 #include <algorithm>
63、 #include <cmath>
64、 using namespace std;
65、
66、 int arc[101][101]; //存放边的权值
67、
68、 typedef struct{
69、 int lowcost; //最短边权值
70、 int adjvex; //最短边的邻接点
71、 }Element;
72、
73、 int Prim(int w, int n){
74、 int i,j,k;
75、 int min;
76、 int length = 0;
77、 Element shortEdge[101];
78、 //初始化顶点w
79、 for(i=0; i<n; ++i){
80、 shortEdge[i].lowcost = arc[w][i];
81、 shortEdge[i].adjvex = w;
82、 }
83、 //加入顶点w
84、 shortEdge[w].lowcost = 0;
85、 for(i=0; i<n-1; ++i){
86、 min = 9999;
87、 //找最短边邻接点
88、 for(j=0; j<n; ++j){
89、 if((shortEdge[j].lowcost != 0)&&(shortEdge[j].lowcost < min)){
90、 min = shortEdge[j].lowcost;
91、 k = j;
92、 }
93、 }
94、 //cout<<shortEdge[k].adjvex<<"--"<<k<<endl;
95、 length+=arc[shortEdge[k].adjvex][k];
96、 //加入顶点k
97、 shortEdge[k].lowcost = 0;
98、 //调整数组shortEdge
99、 for(j=0; j<n; ++j){
100、 if(arc[k][j] < shortEdge[j].lowcost){
101、 shortEdge[j].lowcost = arc[k][j];
102、 shortEdge[j].adjvex = k;
103、 }
104、 }
105、 }
106、 return length;
107、 }
108、
109、 int main()
110、 {
111、 int n;
112、 cin>>n;
113、 for(int i=0; i<n; ++i)
114、 for(int j=0; j<n; ++j)
115、 cin>>arc[i][j];
116、 cout<<Prim(0,n);
117、 return 0;
118、 }
119、 最小生成树----1191
120、 #include <iostream>
121、 #include <cstdio>
122、 #include <cstring>
123、 using namespace std;
124、 const int maxV=505;
125、 const int Max=0x3f3f3f3f;
126、 int arc[maxV][maxV],low[maxV],visit[maxV];
127、
128、 void prim(int n){
129、 int i,j,pos,min,mst=0;
130、 memset(visit,0,sizeof(visit));
131、 pos=1;
132、 visit[1]=1;
133、 for(i=1;i<=n;++i)
134、 low[i]=arc[pos][i];
135、 //查找最短边
136、 for(i=1;i<n;++i)
137、 {
138、 min=Max;
139、 for(j=1;j<=n;j++)
140、 {
141、 if(!visit[j]&&min>low[j])
142、 {
143、 min=low[j];
144、 pos=j;
145、 }
146、 }
147、 mst+=min;
148、 //不连通
149、 if(mst>=Max)
150、 break;
151、 visit[pos]=j;
152、 //更新low
153、 for(j=1;j<=n;j++)
154、 {
155、 if(!visit[j]&&low[j]>arc[pos][j])
156、 low[j]=arc[pos][j];
157、 }
158、 }
159、 //输出
160、 if(mst>=Max)
161、 printf("-1\n");
162、 else
163、 printf("%d\n",mst);
164、 }
165、 int main()
166、 {
167、 int t;
168、 cin>>t;
169、 while(t--){
170、 memset(arc,Max,sizeof(arc));
171、 int n,m,k;
172、 cin>>n>>m>>k;
173、 //新的边
174、 for(int i=0;i<m;i++)
175、 {
176、 int p,q,c;
177、 cin>>p>>q>>c;
178、 if(arc[p][q]>c)
179、 arc[p][q]=arc[q][p]=c;
180、 }
181、 int city[101];
182、 //已连接的边
183、 while(k--){
184、 int numConnected;
185、 cin>>numConnected;
186、 for(int i=1;i<=numConnected;i++)
187、 scanf("%d",&city[i]);
188、 for(int i=1;i<=numConnected;i++)
189、 for(int j=i+1;j<=numConnected;j++)
190、 arc[city[i]][city[j]]=arc[city[j]][city[i]]=0;
191、 }
192、 prim(n);
193、 }
194、 return 0;
195、 }
196、 单源最短路径问题----1077
1. #include <iostream>
2. #include <cmath>
3. #include <queue>
4. #define INF 0x3f3f3f3f
5. using namespace std;
6.
7. const int MAX=1001;
8. int arc[MAX][MAX]={0};
9. int dis[MAX]={0};
10. bool visited[MAX]={0};
11.
12. void dijkstra(int n){
13. queue<int> p;
14. p.push (n);
15. int Present = n;
16. while(!p.empty()){
17. Present = p.front();
18. p.pop ();
19. for(int i=1;i<=n;++i){
20. if(arc[Present][i]!=INF){
21. dis[i] = min(dis[i],dis[Present]+arc[Present][i]);
22. }
23. if(!visited[i]){
24. p.push(i);
25. }
26. }
27. visited[Present] = true;
28. }
29. cout<<dis[1];
30. }
31.
32. int main() {
33. int t, n;
34. cin>>t>>n;
35. //初始化
36. for(int i=1;i<=n;++i){
37. for(int j=1;j<=n;++j){
38. arc[i][j]=INF;
39. }
40. }
41. for(int i=0;i<=n;++i){
42. arc[i][i]=0;
43. }
44. for(int i=1;i<=n;++i){
45. dis[i]=INF;
46. }
47. dis[n]=0;
48. int p1,p2,l;
49. for(int i=0;i<t;++i){
50. scanf("%d%d%d",&p1, &p2, &l);
51. arc[p1][p2] = arc[p2][p1] = l;
52. }
53. dijkstra(n);
全套毕业设计论文现成成品资料请咨询