リュックの問題(発色アルゴリズム)

3968 ワード
python アルゴリズム#アルゴリズム# テキストリンク
作成日:2022年2月25日午後4:04

インプリメンテーションコード

# 가방 문제 (냅색 알고리즘)
import sys
sys.stdin = open("input.txt", "rt")

if __name__ == "__main__":
    N, W  = map(int, input().split())
    dy = [0]*(W+1) # dy[j] 는 가방에 j무게만큼을 담을 수 있을 때 최대 가치
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(w, W+1):
            dy[j] = max(dy[j], dy[j-w]+v)
    print(dy[W])
  • この問題は、同じ種類の宝石を複数回入れることができるという仮定の下で作成されたコードです.
  • 論理
    誰もが
  • 宝石の情報を得ることができ、重要な考えは宝石をバッグに入れると仮定することです.
  • dylistにおいて、dy[j]は、パッケージにj重量を組み込むことができるときの最大の価値を意味する.
    • したがって、
  • は、特定の宝石情報を受信し、その宝石をパッケージに入れると仮定し、dy[j−w]は、パッケージ内の残りの容量での宝石の最大の価値である.dy[j-w]+vは、この宝石を入れた後、宝石を包む総価値である.
  • は、既存のjで計算された容量のパケットの最大値dy[j]と、新しい宝石を加えたときにjで計算された容量のパケットの最大値dy[j-w]+vとを比較し、より高い価値の更新dy[j]値を採用する.
    • 10.コイン交換(発色アルゴリズム)
    アリババと40人の泥棒