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

入力
第1行は、問題の数N(1<=N<=100)およびタイムアウトM(10<=M<=1000)を与える.
2行目からN行で問題を解くと、点数と問題を解くのにかかる時間が得られます.
しゅつりょく
最初の行では、有限時間で得られる最大スコアを出力します.
正解を解く
この大部分は2次元リストで解くが,シェーディングアルゴリズムをMから,つまり最後から2次元リストで解く必要はない.2 Dリストで解決する方法はコメントに残りますが、1 Dリストで解決しましょう.メモリを減らし、スピードを上げましょう.

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

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

繰り返し...

pv現在のスコアを保存します.
pt現在時刻を格納
これにより、以前の最大値と比較して最初の配列を初期化できます.
それはこうなりました.
正しいコード
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を初期化します

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

これはメモリを大量に消費する方法で、結果は前に示したものです.
最初のリストを逆さまに回すのがいいですね.
Reference
この問題について(Part7.11ダイナミックプログラミング(Dynamic Programming)最大スコア(明示的アルゴリズム)を得る), 我々は、より多くの情報をここで見つけました https://velog.io/@angel_eugnen/Part7.8동적프로그래밍DynamicProgramming최대점수-구하기냅색-알고리즘テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol