Skip to main content
 首页 » 编程设计

python之与Python dict的组合总和

2024年11月01日25jillzhang

我有一个梦幻足球(足球)数据的字典,其中元组中的第一个值是价格,第二个是本赛季的预期积分。下面是它的一部分:

 'Romeu': [4.5, 57.0], 
 'Neves': [5.5, 96.0], 
 'Townsend': [6.0, 141.0], 
 'Lucas Moura': [7.5, 105.0], 
 'Martial': [7.5, 114.0], 
 'David Silva': [7.5, 177.0], 
 'Fraser': [7.5, 180.0], 
 'Richarlison': [8.0, 138.0], 
 'Bernardo Silva': [8.0, 174.0], 
 'Sigurdsson': [8.0, 187.0], 

我想做的是编写一个程序,允许我设置价格限制并返回固定长度的组合,例如n=5,得分最高。

因此,如果我将价格限制设置为 32,并且我想要 5 个球员,它会返回 Romeu、Neves、Townsend、Sigurdsson、Fraser。

有人可以给我一个正确方向的提示吗?我不知道如何开始。

请您参考如下方法:

这是我尝试过的一种蛮力方法,从 115 名玩家中选出 5 名玩家(在我的笔记本电脑上用了 1 分 42 秒)。将选择从 100 人中增加到 20 人将需要超过 100,000 年的时间来执行。即使是 50 个中的 20 个也需要 4 天。

from itertools import combinations 
 
# Set the following parameters as desired 
nplayers = 5 
price = 32 
 
players = { 
    'Romeu': [4.5, 57.0], 
    'Neves': [5.5, 96.0], 
    'Townsend': [6.0, 141.0], 
    'Lucas Moura': [7.5, 105.0], 
    'Martial': [7.5, 114.0], 
    'David Silva': [7.5, 177.0], 
    'Fraser': [7.5, 180.0], 
    'Richarlison': [8.0, 138.0], 
    'Bernardo Silva': [8.0, 174.0], 
    'Sigurdsson': [8.0, 187.0], 
} 
 
if len(players) < nplayers: 
    raise IndexError("You selected {nplayers} players but there are only {len(players)} to choose from") 
 
# Create a list of all combinations of players, store as triples (name, cost, score) 
combos = combinations(((h, *t) for h, t in players.items()), nplayers) 
 
top_score = 0 
 
for c in combos: 
    if sum(p[1] for p in c) <= price: 
        score = sum(p[2] for p in c) 
        if score > top_score: 
            top_teams = [c] 
            continue 
        elif score == top_score: 
            top_teams.append(c) 
 
if top_score: 
    print(top_teams) 
else: 
    print(f"You can't afford a team for only {price}") 

输出

[(('Romeu', 4.5, 57.0), ('Neves', 5.5, 96.0), ('Townsend', 6.0, 141.0), ('Fraser', 7.5, 180.0), ('Sigurdsson', 8.0, 187.0))]