/* date:107/10/13 author:Chen Yi Jing 給很多數字,要判斷這些數字是否能分成兩堆等大的數字 1.沒有說一行幾個數字:StringStream 做字串的分割(空白切割) 2.動態規劃 0 1 背包的問題:可以用0-1背包的思想来进行解决。 先将n个数全部累加起来,总数为sum,这里和0-1背包的不同之处在于,这里的价值和重量是一样的, 所以将一个包的容量设置为sum/2,然后你就采用0-1背包思路从n个物品中尽可能的选择数字, 使得数字的和最接近sum/2,那么这个解就是最优解。 */ #include #include using namespace std; int main() { int n = 0; cin >> n; for (int i = 0; i < n; i++) { int temp = 0, index = 0; int weight[20] = {0}; int sum = 0, str = 0; string input; getline(cin, input); //取得一行的輸入 stringstream ss (input); //StringStream 做字串的分割(空白切割) while(ss >> str) { weight[index] = str; index++; } for (int j = 0; j < index; j++) { sum += weight[j]; } if (sum % 2 != 0) { cout << "NO" << endl; } else { cout << "YES" << endl; } cout << sum << endl; //清空 ss ss.str(""); ss.clear(); } }