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

5870 ワード
python algorithm CodingTest テキストリンク

質問する



入力


第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を初期化します

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

    これはメモリを大量に消費する方法で、結果は前に示したものです.
    最初のリストを逆さまに回すのがいいですね.
    thingsboardの使用方法の例
    ARM Cortex-A 9 NEON性能初歩テスト