代码如下:
# 贪心算法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'])