问题描述

有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li， 1<= i<= n。这n 个程序的读取概率分别是p1,p2,…,pn,且pi+p2+…+pn = 1。如果将这n 个程序按 i1,i2,…,in 的次序存放，则读取程序tr 所需的时间tr=c*(Pi1Li2+Pi2Li2+…+Pir*Lir)。这n 个程序的平均读取 时间为t1+t2+…+tn。磁带最优存储问题要求确定这n 个程序在磁带上的一个存储次序，使平均读取时间达到 最小。

数据输入 ：由文件 Input. txt给出输入数据。第1行是正整数n，表示文件个数。接下来的n行中，每行有2个正整数a和b，分别表示程序存放在磁带上的长度和读取概率。实际上第k个程序的读取概率为ak/∑ai.对所有输入均假定c=1

结果输出 ： 将计算的最小平均读取时间输出到文件 output. Txt

	输入文件示例				输出文件示例
	5							
	71   872
	46   452				 85.6193
    9   265
    73   120
    35   85				

算法思想

根据tr计算公式，可知要使平均读取时间最小，即需要使Pi*Li最小的程序放在最前面（最先被读取）
即本题可以通过贪心法来求解。
求解过程：

• 计算每个程序的长度和读取概率的乘积。
• 对序列按照pi*leni升序排序
• 当访问次序确定时，求出每个程序的访问时间。
• 求出n个程序的平均读取时间。

贪心选择性质

贪心选择性质：磁带问题有一个最优解以贪心选择开始

• 命题：磁带问题有一个最优解以贪心选择开始，即包含最小的len*pr，即t0。
• E数组是将磁带上的程序以len*pr非递减排列得到的最优解，E= {t0,t1,t2……tn-1} 。

证明：
对于问题p=∬{ti}，因为问题的解包含了所有的tr，如果只存在一个最优解E，那么序列的顺序是特定的,最优解E一定包含了t0，问题转换为证明最优解唯一。

• 假设
  除E= {t0,t1,…ti……tj…tn-1} 之外还存在一个最优解E’= {t0,t1,…tj……ti…tn-1}，那么访问的时间TE’<=TE，做差TE’-TE=(tj-ti)+(tj-ti)(j-i-1)+{(ti-tj)+(tj-ti)(j-i)}= (tj-ti)(2j-2*i)+1，由于tj>=ti，所以TE’>=TE
  ①若TE’=TE，二者等价于一个最优解
  ②若TE’>TE，与假设矛盾，所以说问题的最优解唯一
  因为只存在一个最优解E，那么序列的顺序是特定的,最优解E一定包含了t0

• 结论：磁带问题有一个最优解以贪心选择开始，即以t0开始

最优子结构性质

最优子结构性质：子问题的最优解可以推导出原问题的最优解
若A是包含于E的一个最优解，则A’ =A-{E[0]}是子问题E’ 的最优解。

• 证明：
  假设在E’ 中找到一个最优解B’，它的平均读取时间比A’ 更小，则将E[0]加入B’中将产生E的一个最优解B={E[0]}+A-{E[0]}，它的平均读取时间比A要更小，这与A的最优性相矛盾。所以每做一步贪心选择都能得到一个更小的，与原问题结构一致的子问题。
• 结论：磁带问题具有最优子结构性质。

局部最优到整体最优

设是p =∬{ti} n个程序的集合，Si是集合{i,i+1,….n-1}中tr最小的程序的时间，A0是包含程序0的最优解，则A0=∪<0,n-1>(Si)，证明A0=∪<0,n-1>(Si) 是最优解。

• 由数学归纳法：
  ①|A|=1，由定理1，成立。
  ②|A|<k,由定理2，成立。
  ③|A|=k,由定理2，A={0}+A1,A1= {S0}+∪<0,n-1>(Si)
  由假设归纳知A0=∪<0,n-1>(Si)
• 结论： A0=∪<0,n-1>(Si)，由局部最优可以得到整体最优。

算法实现

#include<iostream>
#include<queue>
#include<fstream>
using namespace std;
struct  Tape
{
    int len;  //长度
    int pr;  //概率    
    double tr;
    friend bool operator< (Tape a,Tape b) {return a.tr>b.tr;}
    Tape(int l=0,int p=0):len(l),pr(p),tr(l*p){};    
};
priority_queue<Tape>tape;

double minTimeCost(int n,priority_queue<Tape>&tape,long long sum){
    double res=0,acc=0;
    while(!tape.empty())
    {
        acc+=tape.top().tr/sum;//计算tr累加值
        res+=acc;
        tape.pop();
    }
    return res;
}
int main()
{
    int n,a,b;
    long long sum=0;
    ifstream open_file("input.txt");
    open_file>>n;
    for(int i = 0;i<n;i++){
        open_file>>a>>b;
        tape.push(Tape(a,b));
        sum+=b;//计算概率和
    }
    open_file.close();

    double res=minTimeCost(n,tape,sum);

    ofstream out_file("output.txt");
    out_file<<res;
    out_file.close();

    cout<<"tapeOptimalStorage successfuly!"<<endl;
    system("pause");
    return 0;
}

复杂度分析

空间复杂度：T(n)=O(nlogn)，堆排
空间复杂度：S(n)=O(n)，建堆