贪心问题(Python代码实现)——磁带最优存储问题

磁带最优存储问题

设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li， 1≤i≤n。这n 个程序的读取概率分别是p1,p2,…,pn,且p1+p2+…+pn = 1。如果将这n 个程序按 1,2,…,n 的次序存放，则读取程序i所需的时间tr=c*(P1×L1+P2×L2+…+Pr×Lr)。这n 个程序的平均读取时间为 t1+t2+…+tn。实际上第k个程序的读取概率为ak/(a1+a2+…+an)。对所有输入均假定c=1。磁带最优存储问题要求确定这n个程序在磁带上的一个存储次序，使平均读取时间达到最小。试设计一个解此问题的算法,并分析算法的正确性和计算复杂性。

要求：先写出贪心策略，问题建模，Python编写代码，测试数据，测试结果。

贪心策略

每个程序的读取时间都应该找最短

问题模型

1. 计算每个程序的长度和读取概率的乘积。
2. 对1.产生的结果进行排序。
3. 当访问次序确定时，求出每个程序的访问时间。
4. 求出n个程序的平均读取时间。

输入：

第一行一个整数 n
每行有两个整数ai,bi分别表示程序存放在磁带上的长度和读取概率。

输出：
一个结果 表示计算出的最小平均读取时间。

python实现代码

def Sort(a):
    ans=True
    flag=len(a)-1
    while flag>0 and ans:
        ans=False
        for i in range(flag):
            if a[i]>a[i+1]:
                ans=True
                temp=a[i]
                a[i]=a[i+1]
                a[i+1]=temp
        flag-=1
def greed():
    for i in range(n):
        # print(i)
        t[i]=a[i]*b[i]
# print(t[i])
    Sort(t)
# for i in range(n):
# print(t[i])
    for i in range(1,n):
        t[i]+=t[i-1]
 # print(t[i-1])
    to=int(0)
    tp=float(0.0)
    for i in range(n):
        to+=t[i]
        tp+=b[i]
# print(to)
 # print(tp)
    w=float(to)/tp
    print(w)
# def main():
# if __name__=="__main__":
n= int(input())
i=int(0)
w=float(0.0)
t=[0]*n# 
a=[0]*n# 
b=[0]*n# 
for i in range(n):
    a[i],b[i]=map(int,input().split(' '))
greed()
# print(a)
# print(b)
#6
#72 873
#46 462
#9 275
#73 122
#35 84
#23 21
#86.61458900381056

Python知识小结

回顾Python的知识

列表

1. 清空是 t=[0]*n
2. for i in range(1,n):# 从1开始，到n-1 左闭右开
3. a[i],b[i]=map(int,input().split(’ '))//列表输入 两个列表一起 就是 2 4 这个格式的输入
4. a=a = list(map(int, input().split(’ '))) # 单个列表的输入

关于Python sort

1. list .sort(reverse=True) 降序 排序
2. 初始为升序排序 list.sort()

sort()与sorted()的区别

1. 就是sorted() 函数也不会改变所传入的可迭代对象，该函数只是返回一个新的、排序好的列表。

>>> x =[4, 6, 2, 1, 7, 9]
>>> y = sorted(x)
>>> print (y）
[1, 2, 4, 6, 7, 9]
>>> print (x )
[4, 6, 2, 1, 7, 9] 

2. sorted() 函数时，传入一个 reverse 参数，如果将该参数设置为 True，则表示反向排序

>>> sorted(a, reverse = True)
[90, 30, 20, 3.6, 3.5, -1.2]

3. 调用 sorted() 函数时，还可传入一个 key 参数，该参数可指定一个函数来生成排序的关键值

>>> b = ['fkit', 'crazyit', 'charlie', 'fox', 'Emily']
>>> sorted(b, key = len)
['fox', 'fkit', 'Emily', 'crazyit', 'charlie']