算法第四章《贪心策略》上机实践报告

一．实践题目名称

程序存储问题

二．问题描述

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

输入格式:

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

输出格式:

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

三．算法描述（使用什么贪心策略）

输入数据后，用sort函数从小到大进行排列，l表示还剩下长度，sum表示放入的个数，然后从第一个数开始对比，如果小于l就可以将其放入，并将sum++，最后输出sum

#include

#include

using namespace std;

int main()

{

 int n,l;

 cin >> n >> l;

 int s[100]={0};

 for(int i = 0;i < n;i++)

  cin >> s[i];

 sort(s,s+n);

 int sum = 0;

 for(int i = 0;i< n;i++)

 {

  if(l>=s[i])

  {

   sum++;

   l-=s[i]; }

  else

  {

   break;}

 }

 cout << sum;}

四．算法时间及空间复杂度分析

时间复杂度：一个for循环完成数组的遍历与对比，时间复杂度为O（n）。

空间复杂度：算法只使用了普通变量sum记录放入的个数，空间复杂度为O（1）。

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

像这道题一样，我们需要找到一个贪心方案就可以轻松解决，而且在贪心算法这一章里面，经常会用到的就是sort函数进行排序，有些sort函数可以由我们自己进行编写。 

六．对贪心算法的理解和体会

1）贪心算法最重要的是贪心选择性质和最优子结构性质。

2）贪心算法虽然可以很接近最优解，但贪心算法不是万能的，很多条件下或许是不适用的，但我们在做题的时候可以先用贪心算法试一下，如果达不到最优解的话可以改变策略，用动态规划法等方法进行问题的解决。