磁盘最优存储问题---Python

题目描述
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li， 1<= i<= n。这n 个程序的读取概率分别是p1,p2,…,pn,且pi+p2+…+pn = 1。如果将这n 个程序按 i1,i2,…,in 的次序存放，则读取程序ir 所需的时间tr=c*(Pi1Li2+Pi2Li2+…+Pir*Lir)。这n 个程序的平均读取 时间为t1+t2+…+tn。 磁带最优存储问题要求确定这n 个程序在磁带上的一个存储次序，使平均读取时间达到 最小。试设计一个解此问题的算法,并分析算法的正确性和计算复杂性。 编程任务： 对于给定的n个程序存放在磁带上的长度和读取概率，编程计算n个程序的最优存储方案。
输入
由文件input.txt给出输入数据。第一行是正整数n，表示文件个数。接下来的n行中， 每行有2 个正整数a 和b，分别表示程序存放在磁带上的长度和读取概率。实际上第k个程序的读取概率bk/(b1+b2+…+bn)。对所有输入均假定c=1。
输出：
输出一个实数，保留4位小数，表示计算出的最小平均读取时间。

输入样例：
5
71 872
46 452
9 265
73 120
35 87
样例输出：
85.6193

def AverageTime(p,l,n):
    Sum=0
    cost=[0 for i in range(n+1)]
    for i in range(1,n+1):
        #计算读取概率总和
        Sum+=p[i]
    for i in range(1,n+1):
        #计算每个程序的长度与读取概率的乘积
        cost[i]=p[i]*l[i]/Sum   
    #对cost列表升序排序
    for i in range(1,n):
        for j in range(i+1,n+1):
            if cost[i]>cost[j]:
                cost[i],cost[j]=cost[j],cost[i]
                l[i],l[j]=l[j],l[i]
                p[i],p[j]=p[j],p[i]
    #cost.sort()
    time=[0 for i in range(n+1)]
    t=0
    #计算读取每个程序所需的时间
    for i in range(1,n+1):
        t+=cost[i]
        time[i]=t
    Time=sum(time)
    return round(Time,4)

#从文件中读出数据
file_readpath = 'input.txt'
with open(file_readpath) as file:
    txt = file.read()
txt=txt.split('\n')
n=txt[0]
#n代表程序个数
n=eval(txt[0])
#第0个位置不用
l=[0]
p=[0]
for i in range(1,n+1):
    txt1=txt[i].split()
    l.append(eval(txt1[0]))
    p.append(eval(txt1[1]))

#输出结果用于验证
Time=AverageTime(p,l,n)
print("平均存取时间为:",Time)
print("存取的程序顺序为（按长度）",l[1:])
print("存取的程序顺序为（按概率）",p[1:])

#将结果存入文件output.txt
file_writepath = 'output.txt'
file=open(file_writepath,"w")
file.write(str(Time))
file.close()

运行之前新建一个input.txt文件
运行结果如下