Russell_0221

   設有n 個程序{1,2,…, n }要存放在長度為L的磁帶上。程序i存放在磁帶上的長度是 li，1≤i≤n。程序存儲問題要求確定這n 個程序  在磁帶上的一個存儲方案， 使得能夠在磁帶上存儲盡可能多的程序。 對于給定的n個程序存放在磁帶上的長度，計算磁帶上最多可以存儲的程序數。

3.算法描述

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n, L;
    cin>>n>>L;
    int a[n];
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    sort(a, a+n);
    int sum = 0;
    int count = 0;
    for(int i=0; i<n; i++){
        if(sum<L){
            if(a[i]<=L-sum){
                sum += a[i];
                count++;
            }
        }
    }
    cout<<count;
    return 0;
}

   要在規定長度的寬帶上放盡可能多的程序，根據貪心策略，則需要先將長度較小的程序都放進去。

   只要放進去的長度較小的程序足夠多，則能夠取到最優解。

   設sum為當前寬帶中存入的程序長度，count為存入的程序數。

   在運用sort排序后，在for循環中按順序存入長度較小的程序，并同時更新sum和count。

4.算法時間復雜度分析

   因為主要計算量在于將程序長度從小到大的排序，所以算法所需的計算時間為O(nlogn)。

5.心得體會

   貪心策略是通過一系列局部最優解的選擇來獲得整體的最優解，在做題時我們應先確定其是否具有貪心性質，再針對性根據問題來做出貪心選擇即可。