[yukicoder] No.4 おもりと天秤

問題

No.4 おもりと天秤 - yukicoder

動的計画法を使う問題です。

動的計画法は漸化式が有名ですが、二次元となると扱いが難しく感じます。

一度解説を見てJavaで解きましたが、復習を兼ねてPythonで解きました。

考え方

全てのおもりの合計の最大値は なので、 個おもりを天秤に乗せたときに可能な重さを管理することができます。

また、全てのおもりの重さの合計を としたとき、 が偶数でなければ天秤を釣り合わせることができません。

を 個のおもりを天秤のどちらかに乗せたとき、片側の天秤の重さが であるとします。また、

はそのような重さは実現できません。

したがって、

であれば可能です。

コード

N = int(input())
W = list(map(int,input().split()))

sum = sum(W)
if sum % 2 != 0:
    print("impossible")
    exit()

dp = [[0] * 10001 for i in range(N + 1)]
dp[0][0] = 1
idx = 0

for w in W:
    for i in range(10000):
        if dp[idx][i] == 1:
            dp[idx + 1][i + w] = 1
            dp[idx + 1][i] = 1
    idx += 1

if dp[N][int(sum / 2)] == 1:
    print("possible")
else:
    print("impossible")