[Python] 動的計画法 ABC219D

ABC219D

動的計画法で解く。

動的計画法による外部設計は次のようになります。

dpの定義：

dp[i][j][k]=(i番目までの弁当で、たこ焼きはj個、たい焼きはk個食べる最小の個数)

dp漸化式の定義：

dp[i+1][j+A_{i+1}][k+B_{i+1}] = min(dp[i][j+A_{i+1}][k+B_{i+1}], dp[i][j][k] + 1)\\
dp[i+1][j][k] =min(dp[i][j][k],dp[i+1][j][k])\\

ただし、$j+A_{i+1}>X$ でこの弁当を購入するとたこ焼きが $X$ 個を超える場合は $j+A_{i+1}$ の代わりに $X$、$k+B_{i+1}>Y$ でたい焼きが $Y$ 個を超える場合は $k+B_{i+1}$ の代わりに $Y$ にします。

dp初期条件：

dp[0][0][0] = 0\\
dp[i][j][k] = ∞

求める解： $dp[N][X][Y]$
最後に $dp[N][X][Y]=∞$ なら、すべての弁当を買っても目標を達成できないので、-1 を出力します。

計算量は、計算量は $O(NXY)$ です。

サンプルコード(PyPy3)

def main():
    INF = 1000
    N = int(input())
    X, Y = map(int, input().split())
    dp = [[[INF] * (Y + 1) for _ in range(X + 1)] for _ in range(N + 1)]

    mat = []
    for _ in range(N):
        a, b = map(int, input().split())
        mat.append((a, b))

    dp[0][0][0] = 0

    for i in range(N):
        x, y = mat[i]
        for j in range(X + 1):
            jj = min(j + x, X)
            for k in range(Y + 1):
                dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])
                kk = min(k + y, Y)
                dp[i + 1][jj][kk] = min(dp[i + 1][jj][kk], dp[i][j][k] + 1)

    print(dp[N][X][Y] if dp[N][X][Y] < INF else -1)


if __name__ == '__main__':
    main()

本番では解法と外部設計までほぼ模範解答出来たのだが、そこまでに時間を掛け過ぎたこともあり、実装する時間が足りなかった。