Top

(ΦωΦ)＜これの答えですよー。目次はここ。

---
問2-3
#include <iostream>
#include <algorithm>
using namespace std;

int main(void) {
  int n; scanf("%d", &n);
  vector<int> w(n);
  int summa = 0;
  for(int i=0; i<n; i++) {
    scanf("%d", &w[i]);
    summa += w[i];
  }
  if(summa & 1) {
    puts("impossible");
    return 0;
  }
  // i番目を左に置こうか右に置こうか迷っていて、その時点での左の重さがjであるとき
  // dp[i][j] = true
  vector<vector<bool>> dp(n+1, vector<bool>(summa+1, false));
  // 0番目を左に置こうか右に置こうか迷っているとき、左の重さは0である。
  dp[0][0] = true;
  for(int i=0; i<n; i++) {
    for(int j=0; j<=summa; j++) {
      if(dp[i][j]) { // i番目を左に置こうか右に置こうか迷ってるときに、左の重さがjになることがあるのであれば
        dp[i+1][j] = true; // i番目を左に置かなかった(右に置いた)ときは、左の重さはjのままである。
        dp[i+1][j+w[i]] = true; // i番目を左に置いたときは、左の重さはj+w[i]になる。
      }
    }
  }
  // n番目を左に置こうか右に置こうか迷っている(=全部置いた。おもりはn-1番目までしかない！)とき
  // 左の重さがsumma/2になるかどうかを判定する。
  puts(dp[n][summa/2] ? "possible" : "impossible");
  return 0;
}

別解
上の答案を見るとdpテーブルの変化は $i$ も $j$ も増える方向にしか進んでいかないので、
$j$ を大きい方から見ていくようにするとdpテーブルの $i$ の次元を節約できる。
#include <iostream>
#include <algorithm>
using namespace std;

int main(void) {
  int n; scanf("%d", &n);
  vector<int> w(n);
  int summa = 0;
  for(int i=0; i<n; i++) {
    scanf("%d", &w[i]);
    summa += w[i];
  }
  if(summa & 1) {
    puts("impossible");
    return 0;
  }
  vector<bool> dp(summa+1, false);
  dp[0] = true;
  for(int i=0; i<n; i++) {
    for(int j=summa; j>=0; j--) {
      if(dp[j]) {
        dp[j+w[i]] = true;
      }
    }
  }
  puts(dp[summa/2] ? "possible" : "impossible");
  return 0;
}
(ΦωΦ)＜おしまい