《算法设计与分析-贪心法》实验报告

一、实验内容：
贪心法问题。
二、所用算法的基本思想及复杂度分析：
1、 背包问题
1） 基本思想
首先按照单位重量价值对重量和价值数组进行降序排序，然后从大到小依次装入背包直到装不下为止。
2） 复杂度分析
T(n)=O(n)。
2、 客户服务排队问题
1） 基本思想
首先对这n个客户需要的服务时间进行升序排序，然后从小到大开始服务。
2） 复杂度分析
一个while，一个for循环，复杂度都是O(n)，所以总的就是T(n)=O(n2)。
三、源程序及注释：
1、 背包问题
2、 #include <iostream>
3、 #include <algorithm>
4、 #include <cmath>
5、 using namespace std;
6、
7、 int x[10000];   //装入背包的物品
8、
9、 //对数组a[s]~a[m] 与 a[m+1]~a[e]进行归并
10、 void merge(int w[], int v[], int a[], int b[], int s, int m, int e){
11、     int i=s;    //第一个数组起始下标
12、     int j=m+1;  //第二个数组起始下标
13、     int k=s;    //存入b数组的起始下标
14、
15、     //从小到大插入
16、     while(i<=m && j<=e){
17、         if(v[i]/w[i]<=v[j]/w[j]){
18、             a[k] = w[i];
19、             b[k] = v[i];
20、             k++;
21、             i++;
22、         }else{
23、             a[k] = w[j];
24、             b[k] = v[j];
25、             k++;
26、             j++;
27、         }
28、     }
29、
30、     //未插完
31、     while(i<=m){
32、         a[k] = w[i];
33、         b[k] = v[i];
34、         k++;
35、         i++;
36、     }
37、     while(j<=e){
38、         a[k] = w[j];
39、         b[k] = v[j];
40、         k++;
41、         j++;
42、     }
43、 }
44、
45、 //归并排序
46、 void mergeSort(int w[], int v[], int s, int e){
47、     int m, b[10000], a[10000];
48、     if(s==e)
49、         return;
50、     else{
51、         m = (s+e)/2;
52、         mergeSort(w,v,s,m);
53、         mergeSort(w,v,m+1,e);
54、         merge(w,v,a,b,s,m,e);
55、         for(int i=s; i<=e; ++i){
56、             w[i] = a[i];
57、             v[i] = b[i];
58、         }
59、     }
60、 }
61、
62、
63、 int KnapSack(int w[], int v[], int n, int c){
64、     //降序排列单位重量价值
65、     mergeSort(w,v,0,n-1);
66、
67、     int maxValue = 0;
68、     for(int i=0; w[i]<c; ++i){
69、         x[i] = 1;
70、         maxValue += v[i];
71、         c -= w[i];
72、         x[i] = (double)c/w[i];
73、         maxValue += x[i]*v[i];
74、     }
75、     return maxValue;
76、 }
77、
78、 int main(){
79、     //w重量 v价值 n物品数 c背包容量
80、     int w[10000],v[10000];
81、     int n,c;
82、     cin>>c>>n;
83、     for(int i=0; i<n; ++i)
84、         cin>>w[i]>>v[i];
85、     cout<<KnapSack(w,v,n,c);
86、 }
87、 客户服务排队问题
88、 #include <iostream>
89、 #include <algorithm>
90、 #include <cmath>
91、 using namespace std;
92、
93、 int main()
94、 {
95、     int n;  //n个顾客
96、     cin>>n;
97、     int t[1000];    //每个顾客耗费的时间
98、     for(int i=0; i<n; ++i){
99、         cin>>t[i];
100、     }
101、     int count = 0;
102、     while(count!=n){
103、         int min = 9999;
104、         int minj = 0;
105、         for(int j=0; j<n; ++j){
106、             if(t[j]<min){
107、                 min = t[j];
108、                 minj = j;
109、             }
110、         }
111、         cout<<minj<<" ";
112、         t[minj] = 9999;
113、         count++;
114、     }
115、
116、 }
四、运行输出结果：
1、 背包问题

2、 客户服务排队问题

五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：
1、这次的比较简单，暂时没有遇到问题。