与 Python 字典的组合总和

Question

我有一个关于梦幻足球（足球）数据的字典，其中元组中的第一个值是价格，第二个是本赛季的预期积分。下面是它的一部分：

 '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],

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

因此，如果我将价格限制设置为 32，并且我想要 5 名球员，那么 return 是 Romeu、Neves、Townsend、Sigurdsson、Fraser。

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

Answer 1

这是我尝试过的一种蛮力方法，从 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))]

与 Python 字典的组合总和

Combination sum with Python dict

python

dictionary

combinatorics

python-3.x