博客

田忌赛马问题，贪心算法，python

问题描述


胜一场得一分，败一场减一分，平局无得失。给出双方马匹数量，以及每匹马匹的速度，求田忌最多能得多少分。

分析在代码中，采用贪心算法。

import random
n = int(input('请输入马匹数：'))
tj = []   #创建集合收集马匹速度
qw = []
reward = 0
for i in range(0,n):
    tj.append(random.randint(0,100))
    qw.append(random.randint(0,100))

    
tj = sorted(tj)  #升序排序
qw = sorted(qw)

while len(tj):   #循环进行比较，当集合为空时停止

    if tj[0]>qw[0]:   #田忌最慢的比齐王最慢的快，这两只比较，删除
        reward+=1
        del tj[0],qw[0]

    elif tj[0] < qw[0]:     #田忌最慢的比齐王最慢的慢
        if tj[0] == qw[-1]: #田忌最慢的与齐王最快的相等，最慢比最快，删除
            reward+=0
            del tj[0],qw[-1]

        else:
            reward-=1         #田忌最慢的与齐王最快的慢，最慢比最快，删除
            del tj[0],qw[-1]

    elif tj[0] == qw[0]:      #田忌最慢的与齐王最慢相等

        if tj[-1]>qw[-1]:     #田忌最快的与齐王最快相等，最快比最快，删除
            reward+=1
            del tj[-1],qw[-1]

        elif tj[-1] < qw[-1]: #田忌最快的与齐王最快慢，最慢比最快，删除
            
            reward-=1
            del tj[0],qw[-1]

        elif tj[-1] == qw[-1]:#田忌最快的与齐王最快相等

            if tj[0] == qw[-1]:#田忌最慢的与齐王最快相等，最慢比最快，删除
                reward+=0
                del tj[0],qw[-1]

            else:
                reward-=1      #田忌最慢的与齐王最快慢，最慢比最快，删除
                del tj[0],qw[-1]
        

print(reward)

最后通过样例验证，代码正确。

样例

输入：3，【92,83,71】，【95,87,74】 输出：2

输入：2，【20,20】，【20,20】 输出：0

输入：2，【20,19】，【22,18】 输出：0