ソース:https://www.acmicpc.net/problem/2294

質問する

n種類のコインがあります.これらのコインを適当に使って、価値の和をk元にしたいです.同時にコインの個数をできるだけ減らす.コイン1枚につきいくつか使えます.
使用するコインの構成は同じですが、順番が違うのは同じ場合です.

入力

最初の行はn,kを与える.(1≦n≦100,1≦k≦10000)次のn行は、各硬貨に価値を与える.硬貨の価値は100000以下の自然数である.同じ価値のコインが何度も与えられる可能性があります.

しゅつりょく

最初の行で使用したコインの最小個数を出力します.不可能な場合は-1を出力します.

アイデア

NNX KKK行列を用いてdpを実現しようとしたが失敗した.

コード#コード#

Clone

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = []
dp = [10002 for _ in range(k+1)]
for _ in range(n):
    coin = int(input())
    if coin <= k:
        coins.append(coin)
        dp[coin] = 1
for i in range(k+1):
    for coin in coins:
        if i>= coin:
            dp[i] = min(dp[i], dp[i-coin]+1)
if dp[k] == 10002:
    print(-1)
else:
    print(dp[k])

ソース:https://alpyrithm.tistory.com/81

改善