最大スコアを求める(発色アルゴリズム)

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

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

# 최대점수 구하기(냅색 알고리즘) with 2차원 배열
import sys
sys.stdin = open("input.txt", "rt")

if __name__ == "__main__":
    n, m = map(int, input().split())
    dy = [[0 for _ in range(m+1)] for _ in range(n+1)]
    # dy[i][j]는 i번째 문제까지 고려하고 j시간이 주어졌을 때 최대 점수
    for i in range(1, n+1):
        score, time = map(int, input().split())
        for j in range(time, m+1):
            dy[i][j] = max(dy[i-1][j], dy[i-1][j-time]+score)

    print(dy[n][m])

  • 以前の暗い色の問題との違いは、重複しない選択♥2 D配列を作成することで解決しなければならない点です(値を重複しないため)

  • 重複選択があるべきではないのでdy[i][j-time]と比較すべきではなく、以前入力した問題に基づいて比較すべきである.dy[i-1][j-time]と比較

  • 上述したように,2次元配列を作成して問題を解くのが慣例であるが,実戦では空間的複雑度が非常に増加するという問題があるため,1次元配列に簡略化して問題を解く方法もある.

    • 最適な答え(1 D配列を使用)

    # 최대점수 구하기(냅색 알고리즘) with 1차원 배열
import sys
sys.stdin = open("input.txt", "rt")

if __name__ == "__main__":
    n, m = map(int, input().split())
    dy = [0 for _ in range(m+1)]
    # dy[j]는 j시간이 주어졌을 때 최대 점수
    for i in range(0, n):
        score, time = map(int, input().split())
        for j in range(m, time-1, -1):
            dy[j] = max(dy[j], dy[j-time]+score)

    print(dy[m])
  • は非常に簡単な考え方であり、1次元配列を使用して問題を解決することができる.
    • 記入リスト
  • dyは、0番目(前)からではなく、m(後)から記入します.
  • から記入を開始するとdy[j-time]はi題を解いた仮定の下で繰り返し使用される.ただし、後から充填を開始するとdy[j-time]が前の問題に適用されるため、誤った適用を繰り返すことなくdyを充填することができる.
    • FloydWarshallアルゴリズム
    silverlightのナビゲーションコントロールを利用して、ページをめくる効果を実現します