懒得写那么详细了叭 还是多花时间去做算法题去
最优合并问题：
给定k个排好序的序列s1,s2,…,sk，用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并两个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需要的总比较次数最少。
贪心策略：
每次选最小的序列合并得到最少比较次数；
2 个长度分别为m和n的序列需要m + n -1次比较
问题模型：
贪心策略写即可
排好序从小到大
2 个长度分别为m和n的序列需要m + n -1次比较
n = int(input())
a = list(map(int, input().split(' ')))
w=int(0)
i=int(0)
a.sort()#从小到大排序
while(i<n-1):#
w=w+a[i]+a[i+1]-1;#2个长度分别为m和n的序列需要m+n -1次比较
a[i]=a[i]+a[i+1];
a[i+1]=0
i+=1
a.sort()
print(w)
# print(b)
测试数据
5
11 10 4 5 6
测试结果
77
程序存储问题：
设有n 个程序{1，2，…， n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是li1≤i≤n。程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数
贪心策略：从程序长度小开始存储到磁带上
问题：
从小到大排序
每次放入时判断是否超过磁带长度，是则退，否则继续放入
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 main():
# if __name__=="__main__":
n,m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
Sort(a)
sum=int(0)
i=int(0)
cnt=int(0)
for i in range(n):#
if(sum<=m):#如果磁带还可以存储程序
sum+=a[i]
cnt+=1
elif(sum>m):#不可以 则退回加多的 #否则就刚刚好
sum-=a[i]
cnt-=1#退回一个
break#介绍
print(cnt)输入
n,m n是程序个数 m磁带长度
列表 a
# 5 10
# 2 5 4 6 2 列表
# 3 结果最优服务次序问题：
设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1≤i≤n。共有s处可以提供此服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小平均等待时间是n个顾客等待服务时间的总和除以n。
贪心策略：
服务时间越短越好
问题建模：
1.顾客的等待时间n个顾客
2.s个服务取n个顾客做药服务的时间，求平均等待是时间达到最小
3.服务时间从小到大排序
4.达到s个服务出的等待时间
5.求出平均等待时间
Python代码：
# def main():
# if __name__=="__main__":
n,s= map(int,input().split(' '))
a = list(map(int, input().split(' ')))
b=[0]*(n+1)# 服务窗口顾客等待时间
sum=[0]*n# 服务窗口顾客等待时间时间之和
w=int(0)
i=int(0)
j=int(0)
a.sort()
# print(b)
b[0]=1
while(i<n):
if(b[0]==1):
b[j]+=a[i]
else:
b[j]+=a[i]
# print(b[j])
# print(a[i])
sum[j]+=b[j]
i+=1;
j+=1;
if(j==s):#s个服务
j=0
t=float(0)
for i in range(n):
t+=sum[i]
t/=n #平均等待时间
print(t)
测试数据
10 2
2 5 10 45 26 30 108 8 9 12
测试结果
43.9
京公网安备 11010502036488号