読者です 読者をやめる 読者になる 読者になる

UVa10664 Luggage

問題文
http://uva.onlinejudge.org/external/106/10664.html

解法
取る取らないのO(2^20)のDFSで解けばよい。
ちょうど半分に分けられるかどうかを判定するが、ここで入力の重さを安易に整数除算して切り捨てによるミスを犯さないようにする。

ただサンプル1が切り捨てによる違いが現れる形式なのでこの問題の場合ミスしても気づく可能性がある。

#include <bits/stdc++.h>

using namespace std;

int lcnt;
int luggages[21];
int judge;

bool dfs(int idx, int sum) {

  if(idx == lcnt) {
    return sum*2 == judge;
  }
  
  bool ok = 0;
  
  ok = ok || dfs(idx+1, sum+luggages[idx]);
  ok = ok || dfs(idx+1, sum);
  
  return ok;
}

int main() {
  
  int Tc; cin >> Tc;
  while(Tc--) {
    lcnt = 0;
    judge = 0;
    
    for(;;) {
      int a; cin >> luggages[lcnt];
      judge += luggages[lcnt]; lcnt ++;
      char ch; scanf("%c", &ch);
      if(ch == '\n') {
	break;
      }
    }
    
    if(dfs(0, 0)) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  
  return 0;
}