Part7.11ダイナミックプログラミング(Dynamic Programming)最大スコア(明示的アルゴリズム)を得る

質問する

入力

第1行は、問題の数N(1<=N<=100)およびタイムアウトM(10<=M<=1000)を与える.
2行目からN行で問題を解くと、点数と問題を解くのにかかる時間が得られます.

しゅつりょく

最初の行では、有限時間で得られる最大スコアを出力します.

正解を解く

ここでは重要な条件が提示されている.「タイプごとに1つの問題しか解けません」
この大部分は2次元リストで解くが,シェーディングアルゴリズムをMから,つまり最後から2次元リストで解く必要はない.2 Dリストで解決する方法はコメントに残りますが、1 Dリストで解決しましょう.メモリを減らし、スピードを上げましょう.

これらのリストでは、Mから標準値に初期化します.

次のfor文は、初期化された値を参照してmaxを決定します.

繰り返し...

pv現在のスコアを保存します.
pt現在時刻を格納
これにより、以前の最大値と比較して最初の配列を初期化できます.

dy[j] = max(dy[j], dy[j-pt]+ps)
それはこうなりました.

正しいコード

import sys
sys.stdin = open ("input.txt", "rt")

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    N, M = map(int,input().split())
    # M = timelimit
    dy = [0]*(M+1)
    # 한 유형당 한개만 풀수 있다는 조건이 있음!!! 따라서 이차원 테이블을 사용해야 한다.
    # 하지만 이렇게 이차원으로 하다보면 용량이 어마무시하게 커진다. 속도도 느려진다. 따라서 실전에서는 일차원으로 설명해라.

    for i in range(N):
        ps, pt=map(int,input().split())
        for j in range(M, pt-1, -1):
            dy[j] = max(dy[j], dy[j-pt]+ps)
    print(dy[M])

コメント

2 Dリストを使用して重複しないシェーディングアルゴリズムを解く
アルゴリズムは最終的にdy[i−1][j−pt]、すなわち、以前に初期化されたi−1配列の値を参照する.

最初の0行はすべて0に初期化

後でfor文でscoreを初期化します

前の行のレコードの最低価格を参照して初期化を続行すればよい.

これはメモリを大量に消費する方法で、結果は前に示したものです.
最初のリストを逆さまに回すのがいいですね.