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; }