Yukicoder004 おもりと天秤

問題概要

$N$($N\leqq10^2$)個のおもり$w[i]$($w[i]\leqq10^2$)が与えられる。 天秤の両端におもりを全部使って分けたとき、ちょうど釣り合うような置き方は存在するか。

yukicoder004

解法

$dp$[おもさ] :=この重さの重りの割り振り方が存在するか/しないか

として、$dp$をする。 半分の重さがあれば良いので、$sum$ = $\sum$w[i]として、 $sum$が偶数かつ、$dp[sum/2]$が存在すればこのような割り振り方は存在し、 そうでなければ存在しない。 $K$個使ったかどうかの$DP$もできるのだけど、これは無駄。(最初これを書いてしまった。)

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    
    LL N;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VI w(N);
        LL sum = 0;
        FOR(i, 0, N) {
            cin >> w[i];
            sum += w[i];
        }
    
        VI dp(10001, 0);
        dp[0] = 1;
        FOR(i, 0, N) {
            for (int iw = 10000; iw >= 0; iw--) {
                int nw = iw + w[i];
                if (dp[iw]) {
                    dp[nw] = 1;
                }
            }
        }
    
        if (sum % 2 == 0 && dp[sum / 2]) {
            ans = 1;
        }
        cout << (ans ? "possible" : "impossible") << "\n";
    
        return 0;
    }