算法复习题(全)(1)(7)

26 for(i=0;i

29 if(arr[i]

31 temp=arr[i]; 32 arr[i]=arr[j]; 33 arr[j]=temp; 34 } 35 } 36 } 37 } 38

39 void greed(int *arr,int n,int total) 40 {

41 int count,num; 42 int brr[n]; 43 int i;

44 for(i=0;i

46 count=total/arr[i];//硬币的个数

47 total-=arr[i]*count;//更新应找回的钱 48 brr[i]=count;

49 num+=count;//找回硬币总个数

50 printf(\ 51 }

52 printf(\ 53 }

31

3，4章 最大K乘积问题，动态规划，贪心算法 1.动态规划

32

33

2. 贪心算法

34

4章 会场安排，贪心算法

4章 磁带最优存储，贪心算法

简单C++算法代码：时间复杂度为nlogn void GreedySearch(int n,double* p,int& x) {//p为概率，x作为文件排列结果 int k[]; int r,l;

将p[]按非递增序列排列p[k[1]]>=p[k[2]]……>=p[k[n]];

// 这里k1.k2是1，2……n的某一排列 x[n/2]=k[1]; r=n/2+1; l=n/2-1;

for(i=2,i<=n,i+=2) {

x[r]=k[i]; r++; }

for(i=3,i<=n,i+=2) {

x[l]=k[i]; l--; }

35