TDPC A

動的計画法

次のようなアルゴリズムである:

計算結果の記録しながら、帰納的な関係の利用して解く

最適化問題に適用する場合、一般的に、以下の2つが適用する問題に成立していないといけない:

部分構造最適性：部分問題も同じ最適化問題が成立しており、部分問題間が独立している
部分問題重複性：同じ部分問題を繰り返し解く

この２点を満たし、全体の解の形が不明な場合、動的計画法が適している。逆に、全体の解の形が明らかな場合は適さない。適用できるから、適切であるとは限らないことに注意する。部分問題は、サイズを縮小した問題と捉えると良い。実装としては、部分問題の答えの配列をdpとしてメモする形式が多い。

問題の解法

部分和問題とは次のような問題である:

$N$ 個の正の整数 $a_0,…,a_{N−14}$ の中からいくつか選んで総和をとった値を $W$ にできるかどうかを判定せよ

今回の問題は、具体的な整数 W を作れるかどうかを問うのではなく、作れる整数の個数を求める問題となっている。しかし部分和問題が解けていればほとんど解決済みである。なぜなら、部分和問題を解いて得られた配列 $dp[N][j]$ を見ることで、整数 $j$ を作れるかどうかが判定できる。
$i−1$問目までからできる合計点の集合がわかれば、それに $i$ 問目の配点 $p_i$ を足してできる合計点と、足さずにできる合計点を考えることで、$i$ 問目までの問題からできる合計点の集合がわかります。この時、合計点が同じであればどの問題の組み合わせによって出来た点数なのかが関係なくなっているため、解くべき部分問題を減らすことができています。（動的計画法）
動的計画法による外部設計は次のようになります。

dpの定義：
$i$ 問目までの問題を使って、$j$ 点の合計点ができるかどうかの真理値
$$0\leqq i \leqq N, 0 \leqq j \leqq \sum_i p_i$$
dp漸化式の定義：

dp[i][j]=\begin{cases}
        dp[i-1][j]\lor dp[i-1][j-p_i] & (j\ge p_i) \\
        dp[i-1][j] & (j\lt p_i)
        \end{cases}

dp初期条件：

dp[0][0]=1

求める解：$dp[n][j]$が1となる要素数

ここではいわゆる「貰うＤＰ」で、iのループは1からnに増える方向（ボトムアップ方式）で漸化式を考えましたが、配るＤＰや、iのループが逆（メモ化トップダウン方式）でも考えることができます。同じＤＰでもいろいろな解法があることが、汎用性と難解性の要因かと思います。ちなみに、この漸化式だとjのループをMAXから減る方向に回すことで、配列は1次元で済みます。
計算量は、作りうる最大の整数を $W(≤10000)$ として、$O(NW)$ となります。

サンプルコード

# 入力の受け取り
N = int(input())
P = list(map(int, input().split()))

# i問目までの問題を使って、j点の合計点ができるか（bool値）
dp = []
# 0問目は1問も問題を解いていない状態とする。N問あるので、dp[N]まで必要
for i in range(N+1):
    dp.append([False] * (100 * 101))

# 0問目までの問題を使って（=問題を一問も解かない）0点を取ることができる。
# また、それ以外の点数にはならないため、dp[0][0]以外のdp[0]の配列の値はFalseになる。
dp[0][0] = True

# 1問目からN問目までのループ
for i in range(1, N+1):
    # dp[i]に値を入れていくために、dp[i-1]の状態を見ていく
    for j, dpj in enumerate(dp[i-1]): #インデックス,オブジェクトの取得
        if dpj is True:
            # i問目の問題を解かない
            dp[i][j] = True

            # i問目の問題を解く
            # i問目の得点はP[i-1]で表される
            dp[i][j+P[i-1]] = True

# dp[N]の配列を見て、Trueになっているところがありうる合計点
print(dp[N].count(True))

[Python] 動的計画法 TDPC A

TDPC A

動的計画法

問題の解法

[Python] 動的計画法　TDPC A