白準12865号:普通リュック

1509 ワード
テキストリンク
問題解決の考え方
  • ダイナミックプログラミング
  • 分割不可リュック問題(リュック問題)
    • ✔アルゴリズムの説明
    夜勤は苦悶して、どうしても考えが浮かばず、アルゴリズムそのものを勉強しようと決心した.次の図は、与えられた例を求めるプロセスを示す直接描画です.


  • (N+1)x(K+1)寸法を宣言する2次元配列で、デフォルト値はいずれも0です.この場合,赤色に塗った方は実際には不要な数字であるが,コードの一般化のために別途定義する.

  • ドアがN回回ったので、一つ一つのものの重さと価値が得られました.このとき「どのような判断」をして順番に並べます.(以下、この部分について詳しく説明します.)左の黒い字に書かれた数字は1つのものの重さで、円に書かれた値は物の価値です.便宜上、重量の小さい値からミント色→青→青→紫色の順に充填すると仮定します.

  • N番の各ケースにおいて、物品の重量の合計が1〜K(本例では7)の各重量においてとり得る最大値を算出する.このとき、「今まで」のものだけを判断します.(DP)

  • 上記の「いかなる判断」は以下の通りである.
    Case 1:新しく来たものの重量が現在利用可能な重量(1からKまで変化)より大きいと入れられないので、上図の矢印のように、以前の最低価格をそのまま持ってきます.
    Case 2:物を入れることができる場合は、2つの値を比較し、最大値を入れます.
    1つは、自身を入れない前の最大値であり、もう1つは、自身を残りの重量に入れて最大化したときの値である.このとき、残重量を最大化すると、算出された値が利用される.
    • ✔実現コード
    import sys

N, K = map(int, sys.stdin.readline().split())
dp = [[0]*(K+1) for _ in range(N+1)]

for i in range(1, N+1):
    weight, value = map(int, sys.stdin.readline().split())
    for j in range(1, K+1):
        if weight > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight]+value)

print(dp[N][K])
  • の困難なアルゴリズムに比べて、コードは想像以上に簡単です.以上詳しく説明したので,これ以上説明しないようにした.
    • コア点火式
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight]+value)
    ✔関連概念
  • 動的プログラミングにおけるリュックサック問題
    • C++11同時実戦読書ノート(2)
    ExecutorService,Semaphore,CountDownLatchスレッドセキュリティかどうかを測定