python - メモ化を使用した再帰アルゴリズム

Question

私の問題は次のとおりです。それぞれ特定の時間がかかり、特定のポイントを付与するミッションのリストと、それらを実行するために与えられた時間「k」があります。

例： missions = [(14,3),(54,5),(5,4)]およびtime = 15

この例では、3 つのミッションがあり、最初のミッションで 14 ポイントが得られ、所要時間は 3 分です。合計15分あります。各ミッションは、最初の値がこのミッションのポイント数で、2 番目の値がこのミッションの実行に必要な分数であるタプルです。

メモ化を使用して、特定のミッションのリストと特定の時間で取得できる最大ポイントを再帰的に見つける必要があります。

再帰的に動作し、関数 choose_mem(missions,time,mem,k) を使用して目標を達成する choose(missions,time) という関数を実装しようとしています。関数 choose_mem は、選択するミッションの数である 'k' と空の辞書である mem を取得する必要があります。 mem には、以前に解決されたすべての問題が含まれます。

これは私がこれまでに得たものです。上記で必要なものを実装するのに助けが必要です。つまり、辞書の使用法 (現在はちょうどそこにあり、常に空です) と、choose_mem 関数の入力がどこi,j,missions,dにあるべきかという事実です。 choose_mem(missions, time, mem, k)mem = d で、k は選択するミッションの数です。

誰かが私のコードを調整するのを手伝ってくれるなら、それは大歓迎です。

mem = {}

def choose(missions, time):
    j = time
    result = []
    for i in range(len(missions), 0, -1):
        if choose_mem(missions, j, mem, i) != choose_mem(missions, j, mem, i-1):
            j -= missions[i - 1][1]
    return choose_mem(missions, time, mem, len(missions)) 

def choose_mem(missions, time, mem, k): 
    if k == 0: return 0
    points, a = missions[k - 1]
    if a > time:
        return choose_mem(missions, time, mem, k-1) 
    else:
        return max(choose_mem(missions, time, mem, k-1),
                   choose_mem(missions, time-a, mem, k-1) + points)