1

私が持っているこの問題をチェックしてください：

「あなたと 8 歳の甥のエルモは、簡単なカード ゲームをすることにしました。ゲームの開始時に、カードは表向きに長い列に並んで配られます。各カードは、異なる数のポイントの価値があります。カードが配られたら、あなたとエルモは、すべてのカードがなくなるまで、列から左端または右端のカードを順番に取り除きます. 各ターンで、2枚のカードのどちらを取るかを決めることができます. ゲームの勝者はプレーヤーです.ゲーム終了時に最も多くのポイントを集めたカード. アルゴリズムのクラスを受講したことがないので、エルモは明らかな貪欲な戦略に従います.彼の番になると、エルモは常により高いポイント値を持つカードを取ります. あなたの仕事は戦略を見つけることです. (このように小さな子供を殴るのは意地悪に思えるかもしれませんが、エルモは大人に勝たせてしまうのを絶対に嫌がります)。

与えられた最初のカードの並びから、エルモと対戦して獲得できる最大ポイント数を決定するアルゴリズムを説明、解析してください."

この問題の理論的な作業のほとんどは既に完了しています。たとえば、DP に必要なオプティマス部分構造のデモンストレーションを行い、ゲームがどのように行われるかを説明する Recursive 非効率的な形式を定義しました。次のステップは、この問題を効率的に解決するボトムアップ アルゴリズムを設計することです。それが役立つ場合は、トップダウンのメモ化ソリューションを設計することです。私はそれらのどれもできません。この問題をどのように解決しますか？

4

2 に答える 2

0

The algorithm is simple and you can use memoization and dynamic programming in this way:

def findMax(mem, cards, myTurn):
    maxValue = 0
    if(not cards):
        return 0
    if str(cards) in mem: #If we have already compute this state
        return mem[str(cards)]
    elif not myTurn: #turn of Elmo
        if cards[0] > cards[len(cards) - 1]:
            maxValue = findMax(mem, cards[1:], True)
        else:
            maxValue = findMax(mem, cards[:-1], True)
    else: #your turn
        maxValue = max(cards[0] + findMax(mem, cards[1:], False), cards[len(cards) - 1] + findMax(mem, cards[:-1], False))
    mem[str(cards)] = maxValue  #Store the max value for this state
    return maxValue

import random
size = int(10 + random.randint(0,1))
cards = [random.randint(0,50) for x in range(size)]
print "Cards" + str(cards)
print findMax({}, cards, True)

Output:

Cards: [28, 33, 48, 0, 26, 1, 3, 11, 22, 32, 12]
Max value: 120
于 2013-12-09T10:48:29.543 に答える