yukicoder No.4 重りと天秤 解説

問題文

解説

いわゆる部分和問題というタイプのやつ。
まず制約が $N\leqq 100$ なのでbit全探索および再帰関数では厳しそう。
しかし、代わりに $W\leqq 100$ という制約もあるので、dp(動的計画法)で解けると考えられる。
$\text{dp}[i][j]=W_1$~$W_i$ まででjを作ることができるかどうか。
dpの横のサイズは $10001$ もあれば十分。(あり得る解は $0$ ~ $10000$ のため)
$\text{dp}[i][j]$ がtrueなら $\text{dp}[i+1][j]$ もtrue。
$\text{dp}[i][j]$ がtrueなら $\text{dp}[i+1][j+w[i]]$ もtrue。
$(\sum_{i=1}^{N}W_i)\bmod{2}=1$ ならimpossible(事故を防ぐために事前に場合分けしておく)
そうでないなら
$dp[n][\text{sum}/2]$ がtrueならpossible。
そうでないならimpossible。
計算量は $O(N\max(W)^2)$。よって、十分高速。

C++での解答例

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n, sum=0;
  cin >> n;
  vector<int> w(n);
  for(int i = 0; i < n; i++) {
    cin >> w[i];
    sum += w[i];
  }
  if(sum % 2 == 1){
    cout << "impossible\n";
    return 0;
  }
  vector<vector<bool>> dp(n+1, vector<bool>(10099, false));
  dp[0][0] = true;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j <= 10000; j++) {
      if(!dp[i][j])continue;
      dp[i + 1][j] = true;
      dp[i + 1][j + w[i]]=true;
    }
  }
  cout<<(dp[n][sum / 2] ? "possible\n": "impossible\n");
}