算法第四章上机实践报告

程序存储问题

1.实践题目

设有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
2.问题描述
先按程序的大小从小到大排序，每次贪心选择一个最小的程序加入磁带内，直到磁带装不下下一个程序。
3.算法描述

#include<bits/stdc++.h>
using namespace std;
int a[50000];
int main()
{
    int n,m,cnt=0,sum=0;
    cin >> n >> m;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        sum+=a[i];
        
        if(sum>m) 
            break;
        else    
            cnt++;
    }
    cout << cnt << endl;
    return 0;
} 

贪心策略：每次选择程序存放在磁带上的长度最小的程序进入磁带

反证法证明贪心选择性质以及最优子结构性质

设程序集合E = { 1, 2, 3, ..., n} 以按程序长短的非减序顺序排序，程序1具有最短长度。

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

设A ⊆ E是全局最优解且A中最短的程序是k。

（1）若k = 1，则全局最优解中包含程序1

（2）若k > 1, 则把k拿掉后剩下的集合与程序1是装得下在同一个磁带上的。（因为k是全局最优解A中最短程序，但k > 1, 说明在排序集合E中1的程序长度比k的程序长度还小，把k从A中拿掉后，还剩k容量，1会装的下，因为排序集合E中1的程序长度比k的程序长度还小）此时全局最优解为B = A - {k} ∪ {1}

无论全局最优解A/B，都含有最优解程序1

2、若A是原问题包含程序1的最优解，则A‘ = A - {1}，是子问题E’ = {2, 3, ...n}的局部最优解。

若不是，就设B‘是E‘的解且|B‘| > |A‘|（这时候B‘更有能力胜过A‘),则B‘ ∪ {1} 是E的全局最优解且有|B‘| + 1 >  |A|。此结果与A是全局最优解矛盾。

故该贪心算法得证。

4.算法时间及空间复杂度分析

其贪心算法的主要计算量在于将程序存放在磁带上的长度从小到大排序，故算法所需的计算时间为O(nlogn）。

该算法的临时空间随着n的改变而增大，都要创建一个与之对应的数组，故空间复杂度为O(n）。

5.心得体会

学会了优先队列的使用。

算法第四章上机实践报告

原文：https://www.cnblogs.com/lycsuper/p/11845945.html