yukicoder 0004 おもりと天秤
問題文概要
$w_1, \dots, w_n$ が与えられる. このなかからいくつか選び, 和を $(\sum_i w_i) / 2$ に出来るか.
制約
$2 \le n \le 10^2$, $1 \le w_i \le 100$.
解法
ナップサックのような DP をする.
ソースコード
1
2
3
4
5
6
7
8
9
10
11
12
bool solve(){
int n;
cin >> n;
vector<int> w(n);
for(aur x : w) cin >> x;
const int m = accumulate(all(w), 0);
vector<int> dp(m*3, 0);
dp[0] = 1;
for(aur x : w) for(int i = m; i >= 0; --i) dp[i+x] |= dp[i];
cout << (m % 2 == 0 and dp[m/2] ? "possible" : "impossible") << endl;
return true;
}