算法第四章上机实践报告

一、实践题目

二、问题描述

（1）题目关键字：①n个程序 ②长度为L ③程序i存放在磁带上的长度是li ④磁带上最多可以存储的程序数

（2）思路：定义文件个数n、磁带长度L和n个程序存放在磁带上的长度，按照题目要求输入文件个数n和磁带长度L，然后开辟数组存储空间，将数组内的元素全部初始化为1000（以便后续用sort算法排序后前n个元素仍是题目提及的n个程序），并根据文件个数逐个输入程序存放在磁带上的长度。初始化最多可以存储的程序数sum，初始化k，通过k存放并叠加循环过程中不同程序（不能超过磁带长度）在磁带上的长度，在循环开始前通过sort排序算法将n个程序按长度从小到大的顺序进行排序。排序完毕，通过n次循环（因为有n个程序）逐个选择长度最短的程序进行存放，如果k的值未超出磁带长度，则sum的值+1，否则退出循环，最终输出最多可以存储的程序数sum。

三、算法描述

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    
    int n,L,a[50];// 定义文件个数n、磁带长度L和n个程序存放在磁带上的长度 
    cin>>n>>L;//输入文件个数n和磁带长度L 
    
    for(int i=0;i<50;i++)
    {
        a[i]=1000;
    }
    //开辟数组存储空间，将数组内的元素全部 初始化 为1000
    //以便后续用sort算法排序后前n个元素仍是题目提及的n个程序 
    
    for(int i=0;i<n;i++)
    {
        cin>>a[i];//逐个输入程序存放在磁带上的长度
    }
    
    int sum=0,k=0;
    //初始化最多可以存储的程序数sum 
    //初始化k
    //通过k存放并叠加循环过程中不同程序（不能超过磁带长度）在磁带上的长度
     
    sort(a,a+L);//通过sort排序算法将n个程序按长度从小到大的顺序进行排序 
    
    for(int i=0;i<n;i++)
    {
        k += a[i];
        //因为要存储最多的程序数，所以每次会先选择长度最短的程序进行存放 
        if(k<=L) 
            sum +=1;//未超出磁带长度，可存储程序数+1 
        else
            break;
    }
    
    cout<<sum;//输出最多可以存储的程序数 
    return 0;
}

（1）贪心策略：每次挑选长度最短的程序进行存放

（2）反证法证明贪心选择和最优子结构性质：

设E=｛1，2，...，n｝为所给的程序集合。由于E中程序按长度大小的非减序排列，故程序1具有最短长度。首先证明程序存储问题有一个最优解以贪心选择开始，即该最优解中包含程序1。设AE是所给的程序存储问题的一个最优解，且A中程序也按长度大小非减序排列，A中的第一个程序是程序k。若k=1，则A就是一个以贪心选择开始的最优解。若k>1，则设B=A-{k}∪{1}。由于f1≤fk，则A中程序是相容的，故B中的程序也是相容的。又由于B中程序个数与A中程序个数相同，且A是最优的，故B也是最优的。也就是说，B是以贪心选择程序1开始的最优程序存储。由此可见，总存在以贪心选择开始的最优程序存储方案。

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

时间复杂度：O(nlogn)

这道题目的关键算法是算法，该算法主要计算时间在于将程序依其长度大小从小到大排序，算法的计算时间上界为O(nlogn)。

空间复杂度：O(1)

整个贪心算法只使用了变量k记录每次循环找到的局部最优解，所以空间复杂度为O(1)。

五、心得体会

在做这道题的时候，刚开始有一个不太熟悉和理解的做法是在测试程序开辟数组存储空间时，要将数组内的元素全部初始化为1000。后来在写实践报告和询问了组队的伙伴之后，才知悉了原因：如果一开始不将新建的数组元素全部初始化为1000，可能会导致在使用sort算法对程序进行排序时本应出现在数组前面的元素所有值都会是默认初始值0，最终导致无法输出贪心算法对应的最优解。通过这次上机实验，我在一定程度上掌握了贪心算法的使用和相应的规律，通过对程序存储问题的求解，使我对贪心算法有了进一步的了解，并且了解到贪心算法的重要性。

算法第四章上机实践报告

原文：https://www.cnblogs.com/RenaJun/p/11872081.html