Part7.10ダイナミックプログラミング(Dynamic Programming)コイン交換(明示的アルゴリズム)

質問する

入力

1行目はコインの種類数N(1<=N<=12)を与える.2行目はNコインの時計です
クラスは与えられ、次の行は探す金額M(1<=M<=500)が与えられる.
コインの種類は100元を超えない.

しゅつりょく

最初の行に探しているコインの最小個数を出力します.

正解を解く

イントラカラーアルゴリズムを使用します.
発色アルゴリズムは面白いと思います

正しいコード

import sys
sys.stdin = open ("input.txt", "rt")

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n = int(input())
    coin = list(map(int,input().split()))
    m = int(input())
    dy=[1000]*(m+1)
    dy[0]=0

    for i in range(n):
        for j in range(coin[i], m+1):
            dy[j] = min(dy[j], dy[j-coin[i]]+1)
    print(dy[m])

コメント

シェーディングアルゴリズムの説明
色分けアルゴリズムは入れられるものによって区別されない.
収納可能アイテムが分割された場合(砂糖数グラムなど):分割可能リュックの問題(Fractional Knapsack Problem)
入れられるものが分割できない場合(入れない場合):0-1バックパックの問題(0-1 Knapsack Problem)
この問題は0-1リュックサックの問題です.
この問題は以下のアルゴリズムで解くことができる.説明します
アルゴリズム#アルゴリズム#
1)x軸において、バッグの重量は1~K、y軸は物品のN個数の配列である.
2)順番に迂回し、以下のアルゴリズムを実行する.
3-0)現在のアイテムが現在の回転の重量より小さい場合は、[先行アイテム][同重量](リュックサック[i-1][j]を入力します.
3-1)現物を入れる.荷物を入れた残りの重量(リュックサック[i-1][j-weight])は、上の行から取って満タンにします.
3-2)今のものより.他のもので埋めた値(リュックサック[i-1][j]).
4)リュックサック[i][j]に3-1と3-2のより大きな値を保存する.この値段は今までに物で构成された最も価値のある配置です.
5)バックパック[N][K]とは、K重量時の最低価格のこと.
に飾りを付ける
最終的に式で次のように表現されます.
バックパック[i][j]=max(現物価値+バックパック[古物][現物バックパック重量-現物重量]、バックパック[古物][現物バックパック重量])
knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])
最終的には以下のようなアクセルが発生する.