算法第四章上机实践报告

一、实践题目

程序存储问题：设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。

输入格式:

第一行是2 个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。

输出格式:

输出最多可以存储的程序数。

输入样例:

在这里给出一组输入。例如：

6 50 
2 3 13 8 80 20

输出样例:

在这里给出相应的输出。例如：

5

二、问题描述

通过合理地选择安排程序，使长度一定磁带上存储尽可能多的程序，求最多可以存储的程序数。

三、算法描述（说明你的贪心策略，并且参考会场安排问题，利用反证法证明贪心选择和最优子结构性质）

贪心策略：选择可选的程序中长度最小的那个

反证法证明：

　　设程序集合E=｛1，2，...，n｝以按长度大小的非减顺序排列，程序1具有最短的长度。

　　1、首先必有最优解包含程序1

　　不然设AE是最优解且A中最短的程序是k。若k=1，则最优解包含程序1，若k>1，则程序1必比程序k短，可以代替程序k，令B=A-{K}+{1},则B也是一个最优解。

　　2、进一步，若A是原问题的包含程序1的最优解，则A‘=A-{1}是活动集合E‘=E-{1}的最优解

　　不然设B‘是E‘的解且|B‘|>|A‘|,则B‘∪{1}是E的解且|B‘|+1>|A|,此与A是最优解矛盾。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 int a[10001];
 6 
 7 int main()
 8 {
 9     int n; 
10     cin >> n;
11     int L;
12     cin >> L;
13     for(int i = 0; i < n; i++)
14     {
15         cin >> a[i];
16     }
17     sort(a, a+n);
18     int in = 0;
19     int count = 0;
20     for(int j = 0; j < n; j++)
21     {
22         if(a[j] <= L - in)
23         {
24             in = in + a[j];
25             count ++;
26         }
27     }
28     cout << count;
29     return 0;
30 }

四、算法时间及空间复杂度分析（要有分析过程）

时间复杂度：初始化数组时使用了for循环语句，时间复杂度为O(n),在将程序填入磁带时，使用了for循环语句,时间复杂度也为O（n),所以整个算法的时间复杂度为O（n)。

空间复杂度：因为需要用到一维数组来存储程序长度，所以空间复杂度为O（n)。

五、心得体会（对本次实践收获及疑惑进行总结）

1、在我看来，贪心算法主要是难在想出怎样才是当前的最好选择，面对与老师讲过例题相似的题目还可以依葫芦画瓢，但是遇到全新的问题就还是不知道该如何下手，我觉得应该还是我见的题目少了，同时数学思维有所欠缺。而通过这次的实践，我对于贪心算法有了更深入地理解，对于一些题目类型，也掌握了解题套路。希望自己以后可以花更多的时间去动手打代码吧，算法光看书果然是不行的！

2、这次实践主要是卡在了第二题。首先是思维定势，认为输入的一定要是整数，就使得整个代码很冗长，多了很多不必要的处理，处理越多，就越容易出现错误，这就使我们花费了许多时间。还有就是我们思考不够全面，没有想到结果为0的情况，就一直在那看代码。可就是找不到错在哪......今天的教训都是未来的经验，希望自己以后思考问题可以不再局限，更加细心。