贪心问题(Python代码实现)—— 最优合并问题- 程序存储问题- 最优服务次序问题

懒得写那么详细了叭还是多花时间去做算法题去
最优合并问题：
给定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)

测试数据

11 10 4 5 6

测试结果

程序存储问题：

设有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)