ABC286 D問題 Money in Hand

動的計画法(DP)を考える

問題：N 種類の硬貨を組み合わせて、ちょうど X 円にできるか。

これは、動的計画法(DP)を使うとよい問題です。（「競技プログラミングの鉄則」4.4 ナップザック問題）
「1,2,...,p の p 種類の硬貨で q 円にできるかどうか」を表す二次元配列 dp[p][q] を作成していきます。
「できるかどうか」が問題なので、dp は true か false を表すBool型 (論理型) の配列でかまいません。

p - 1 種類の硬貨で q 円にできるか dp[p-1][q] ( q = 0,1,2,...,X ) がすでに得られているとします。
これに p 種類目の硬貨を追加すると、dp[p-1][q] が true のとき、 dp[p][q + k * A] が true になります。
(k は硬貨の枚数= 0, 1, ...、 A は硬貨の額面 )
硬貨の種類を増やしていって、最終的に dp[N][X] が true なら可能、 false なら不可能となります。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  # 入力データ
  N, X = readInts()
  A = Vector{Int}(undef,N)
  B = Vector{Int}(undef,N)

  for i = 1:N
    A[i], B[i] = readInts()
  end

  # 動的計画法 (dp)
  dp = falses(N,X)

  for i = 1:N        # 硬貨の種類

    # この硬貨のみ

    for k = 1:B[i]   # 硬貨の枚数
      P = A[i] * k

      if P > X  # X 円を超えたらforループを抜ける
        break
      end

      dp[i,P] = true

    end

    # i-1 までの硬貨 + この硬貨(0 枚の場合も含む)

    if i > 1
      for j = 1:X
        if dp[i-1,j]
          for k = 0 : B[i]

            P = j + A[i] * k

            if P > X  # X 円を超えたらforループを抜ける
              break
            end

            dp[i,P] = true

          end
        end
      end
    end
  end

  # dp[N,X] が true の場合、N 種類のコインで X 円 支払える

  if dp[N,X]
    println("Yes")
  else
    println("No")
  end

end  # function solve


# main
solve()