python - 列表索引越界(街机游戏)

Question

我最近参加了一个面试，被问到以下问题:

Adam 非常擅长玩街机游戏，他玩的每场游戏都会赢。一个晴朗的日子，当他走在街上时，他发现了一家街机商店，玩家每赢一场游戏就会支付真金白银——然而，这家商店每场比赛只支付一次。商店有一些游戏，他们会为获胜者支付奖金，每个游戏都有自己的完成时间和支付率。亚当对通过自己的才能赚钱的前景感到兴奋，他走进商店才发现商店将在 2 小时(正好 120 分钟)后关门。知道他不能在那段时间玩所有游戏，他决定选择能使他的收入最大化的游戏

街机游戏板示例游戏完成_TIME(以分钟为单位)PAYOUT_RATE

Pac-man 90  400
Mortal Kombat   10  30
Super Tetris    25  100
Pump it Up  10  40
Street Fighter II   90  450
Speed Racer 10  40

一种可接受的解决方案是，即使游戏列表或完成时间或支付率发生变化，它仍会选择最佳 yield 。

问题:用 Java/Scala/Python 编写代码，帮助 Adam 选择最赚钱的游戏序列。

然后，假设您有一个可变的游戏列表及其支付率。选择最赚钱的游戏的最佳方法是什么？

输入说明:输入的第一行始终是一个整数，表示在第一行之后要读取的行数。在我们的示例测试用例中，第一行有 6 行，第一行之后有 6 行，每行都有一个游戏、completion_time 和 payout_rate。在每一行数据中，游戏、完成时间和支付率由“,”(逗号)分隔。游戏板可能会改变，但商店仍会在 120 分钟后关门。

输入:6

Pac-man,80,400
Mortal Kombat,10,30
Super Tetris,25,100
Pump it Up,10,40
Street Fighter II,90,450
Speed Racer,10,40

输出说明:按字母顺序将他赚得最多的游戏名称打印到标准输出中

输出

Mortal Kombat
Pump it Up
Speed Racer
Street Fighter II

到目前为止尝试过:

import sys
import itertools

line = sys.stdin.readline()
def biggest_payout(line):
   
    a = line.split(sep=' ')
    b = []
    for i in range(1, len(a)):
        b.append(a[i].split(sep=','))
    c = []
    for i in range(len(b)):
        c.append(int(b[i][1]))
    min_sums = []
    for L in range(0, len(c)+1):
        for subset in itertools.permutations(c, L):
            min_sums.append(sum(subset))
    e = []
    for i in range(len(b)):
        e.append(int(b[i][2]))
    money_sums = []
    for L in range(0, len(e)+1):
        for subset in itertools.permutations(e, L):
            money_sums.append(sum(subset))
    k = []
    for i in range(len(b)):
        k.append(b[i][0])
    movie_combos = []
    for L in range(0, len(k)+1):
        for subset in itertools.permutations(k, L):
            movie_combos.append(subset)   
    while True:
        if min_sums[money_sums.index(max(money_sums))] > 120:
            money_sums[money_sums.index(max(money_sums))] = 0
        else:
            index = money_sums.index(max(money_sums))
            break
    return movie_combos[index]

for line in sys.stdin:       
       print(biggest_payout(line))

错误:

  File "/temp/file.py", line 13, in biggest_payout
    c.append(int(b[i][1]))
IndexError: list index out of range

我的数组索引越界，请问有人能指导我如何解决这个问题吗？

Answer 1

你不应该用 ' ' 分割行，你的代码还有更多问题。

此外，排列将包含(Pac-man, Mortal Kombat) 和 (Mortal Kombat, Pac-man) 等。我会而是使用组合(在这种情况下，组合比排列少 10 倍)并编写类似这样的内容。

import sys
import itertools

n = int(sys.stdin.readline())

games = {}
for i in range(n):
    s = sys.stdin.readline().rstrip().split(',')
    games[s[0]] =  (int(s[1]), int(s[2]))

res = ()
maxpay = 0

for k in range(1, n):
    for z in itertools.combinations(games, k):
        time = 0
        pay = 0
        for x in z:
            time += games[x][0]
            if time > 120:
                break
            pay +=  games[x][1]
        if time <= 120 and pay > maxpay:
            res = z
            maxpay = pay

print('\n'.join(sorted(list(res))))

测试。

$cat data 
6
Pac-man,80,400
Mortal Kombat,10,30
Super Tetris,25,100
Pump it Up,10,40
Street Fighter II,90,450
Speed Racer,10,40

$python3 solution.py < data
Mortal Kombat
Pump it Up
Speed Racer
Street Fighter II