一、实验内容：
贪心法问题。
二、所用算法的基本思想及复杂度分析：
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、这次的比较简单，暂时没有遇到问题。
