我是菜鸟,帮我用python实现一个贪心算法的demo?

bluesky1年前 ⋅ 1031 阅读
代码如下:

# 贪心算法demo
# 贪心算法是一种在每一步中选择当前最优解的算法
# 以下例子为有10个站点,每个站点都有不同距离和分数
# 以距离最近为第一优先级,分数最大为第二优先级

#定义站点及相关参数
#站点1
Station1 = {
    'name': 'Station1',
    'distance': 15,
    'score': 3
}
#站点2
Station2 = {
    'name': 'Station2',
    'distance': 10,
    'score': 4
}
#站点3
Station3 = {
    'name': 'Station3',
    'distance': 20,
    'score': 6
}
#站点4
Station4 = {
    'name': 'Station4',
    'distance': 5,
    'score': 5
}
#站点5
Station5 = {
    'name': 'Station5',
    'distance': 8,
    'score': 2
}
#站点6
Station6 = {
    'name': 'Station6',
    'distance': 12,
    'score': 6
}
#站点7
Station7 = {
    'name': 'Station7',
    'distance': 11,
    'score': 3
}
#站点8
Station8 = {
    'name': 'Station8',
    'distance': 18,
    'score': 6
}
#站点9
Station9 = {
    'name': 'Station9',
    'distance': 7,
    'score': 5
}
#站点10
Station10 = {
    'name': 'Station10',
    'distance': 17,
    'score': 4
}

# 距离最近为第一优先级,分数最大为第二优先级
Stations = [Station1, Station2, Station3, Station4, Station5, Station6, Station7, Station8, Station9, Station10]

# 初始化
selectedStations = [] # 用于存储结果的list
minDistance = None # 当前最小的距离
maxScore = None # 当前最大的分数

# 贪心算法:遍历所有站点,每次比较距离和分数,选择距离最近且分数最大的站点
for station in Stations:
    if minDistance is None or station['distance'] < minDistance:
        selectedStations.append(station)
        minDistance = station['distance']
        maxScore = station['score']
    elif station['distance'] == minDistance and station['score'] > maxScore:
        selectedStations.pop()
        selectedStations.append(station)
        maxScore = station['score']

# 输出最终选择的结果
print('最终的站点为:')
for station in selectedStations:
    print(station['name'])

全部评论: 0

    相关推荐