列表索引越界（街机游戏）

Question

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

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

游乐场的示例游戏板游戏 COMPLETION_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

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

问题：在 Java/Scala/Python 中编写代码以帮助 Adam 选择最赚钱的游戏序列。

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

输入说明：输入的第一行始终是一个整数，表示在第一行之后要读取的行数。在我们的示例测试用例中，第一行有 6 行，第一行之后有 6 行，每行都有一个游戏，completion_time 和 payout_rate。在每个数据行中，游戏、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

列表索引越界（街机游戏）

List Index out of Bounds (Arcade game)

python

algorithm

list

knapsack-problem

python-3.x