51 lines
1.4 KiB
C++
51 lines
1.4 KiB
C++
/*
|
||
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 <iostream>
|
||
#include <sstream>
|
||
|
||
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();
|
||
}
|
||
}
|
||
|