yls 算法设计与分析实验指导(8)

2019-05-17 19:24

实验五：贪心算法和随机算法

1. 背包问题

有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品重量价值 A 35 10 B 30 40 C 60 30 D 50 50 E 40 35 F 10 40 G 25 30 2. #include 3. #include 4. #define N 7 5. #define C 150 6. float weight[7]; 7. float value[7]; 8. float pervalue[7]; 9. int n,a[7]; 10. float max=0; 11. void readdata() 12. {

13. int i;

14. for(i=0;i

24. for(i=0;i

28. void sort() 29. {

30. int i,j,t;

31. for(i=0;i

33. for(j=i+1;j

34. if(pervalue[j]>pervalue[a[i]]) 35. {

36. t=a[i]; 37. a[i]=a[j]; 38. a[j]=t; 39. } 40. } 41. } 42. 43.

44. float search() 45. {

46. int i,j;

47. float con,val; 48. for(i=0;i

50. con=weight[a[i]]; 51. val=value[a[i]]; 52. for(j=i+1;j

53. if(weight[a[j]]<(C-con)) 54. { 55. con+=weight[a[j]]; 56. val+=value[a[j]]; 57. }

58. else { 59. val=val+(pervalue[a[j]])*(150-con); 60. con=150; 61. }

62. if(max

64. printf(\65. return (max); 66. } 67.

68. void main() 69. { 70. int i; 71. float v;

72. /* scanf(\73. for(i=0;i

79. printf(\

80. //}

81. }照亮的山景

在一片山的上空，高度为T处有N个处于不同位置的灯泡，如图。如果山的边界上某一点于某灯i的连线不经过山的其它点，我们称灯i可以照亮该点。开尽量少的灯，使得整个山景都被照亮。山被表示成有m个转折点的折线。

提示：照亮整个山景相当于照亮每一个转折点。

#include int M,N; int b[100];

float left,right,x[100],y[100],qian[50],hou[50],top=40.0; void readdata() { int i; printf(\输入折点的个数：\ scanf(\

intf(\输入每个折点的坐标：\

for(i=0;i

left=-9999;//设置左端无穷远点 right=9999;//设置右端无穷远点 }

creatqujian()//创建区间

{ int i; int num=0; for(i=1;iy[i]||y[i+1]>y[i])//判断为凹点

{ qian[num]=(x[i-1]-x[i])*(top-y[i])/(y[i-1]-y[i])+x[i]; if(qian[num]>x[i]) qian[num]=left; //求得左端点 hou[num]=(x[i+1]-x[i])*(top-y[i])/(y[i+1]-y[i])+x[i]; if(hou[num]

return (num); }

void sortqujian()//对区间按右端点由小到大排序 { int i,j,t; for(i=0;i

int search()

{ int i,j; int num=0,tag=0; int used[100]={0}; for(i=0;i

//对于排好序的区间，检查其后点所能同时找到的区间，并标记 if(!used[b[i]])

{ for(j=i+1;j=N)break; } printf(\ return (num); }

void main() { int num=0; int spot; readdata();

N=creatqujian(); sortqujian(); spot=search();

printf(\ }

82. 搬桌子问题

某教学大楼一层有n个教室，从左到右依次编号为1、2、…、n。现在要把一些课桌从某些教室搬到另外一些教室，每张桌子都是从编号较小的教室搬到编号较大的教室，每一趟，都是从左到右走，搬完一张课桌后，可以继续从当前位置或往右走搬另一张桌子。输入数据：先输入n、m，然后紧接着m行输入这m张要搬课桌的起始教室和目标教室。输出数据：最少需要跑几趟。

Sample Input 10 5 1 3 3 9 4 6 6 10 7 8

Sample Output 3

分析：贪心算法，把课桌按起点从小到大排序，每次都是搬离当前位置最近的课桌。程序如下： #include int main() { struct { int start; int end; }a[100]; int i,j; int n,m,min,num,temp,used[100]={0}; scanf(\

for(i=0;i

// sort(a,n); //按start从小到大对数组a排序 min=0; num=0; while(num=temp) { temp=a[i].end; used[i]=1; num++; } min++; } printf(\}

83. 用随即算法求解8皇后问题 84. 素数测试最小生成树

#include struct Edge

{ int from, to, weight;

//定义一个数据结构，存放点和边的关系以及边的权值

}; Edge edge[100], temp; //用定义的数据结构来定义一个数组和一个变量 int i, j, n, m; int p[100]; int seek(int x) //用来找出当前端点所在集合编号

{ if(p[x]==x) return x;

else return p[x]=seek(p[x]); }

int Kruskal() { int x, y,k=0; for(i=0;i<100;i++) p[i]=i; for(i=0;i

{

共8页:

yls 算法设计与分析实验指导(8).doc 将本文的Word文档下载到电脑下载失败或者文档不完整，请联系客服人员解决！

下载这篇word文档