题目来源：http://poj.org/problem?id=1014
题目大意：
Marsha和Bill拥有一些弹珠。但是这些弹珠的价值不一样。每个弹珠的价值都是1到6之间的自然数。他们希望把这些弹珠分为两份，每份的总价值相等。然而，有时候是不存在这样的划分的（即使总的价值为偶数）。比如弹珠的价值分别为1,3,4,4.写一个程序判断一些弹珠是否可以被分为价值相等的两份。
输入：每行代表一个测试用例，含6个非负整数。n1,...n6.ni表示价值为i的弹珠有多少个。测试用例最多20000个。输入以“0 0 0 0 0 0”结束。
输出：对于每个用例，若可分，输出： "Collection #k:", 其中k为用例编号， "Can be divided." 或 "Can't be divided."每个用例输出之后接一个空白行。
Sample Input
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
Sample Output
Collection #1:
Can't be divided. Collection #2:
Can be divided.
首先，如果弹珠的总价值为奇数一定不可分，然后，用dfs搜索，找出所有弹珠中的一个子集，使其和为总价值的一半，若能找到则可分，反之不可分。
//////////////////////////////////////////////////////////////////////////
// POJ1014 Dividing
// Memory: 596K Time: 0MS
// Language: C++ Result: Accepted
////////////////////////////////////////////////////////////////////////// #include <iostream> using namespace std; int stone[];
int totalValue;
bool flag = false; bool dfs(int sum, int s, int target) {
if (flag) return true;
if (sum == target) {
return true;
}
for (int i = s; i >; --i) {
if (stone[i - ]) {
if (sum + i <= target) {
--stone[i - ];
if (dfs(sum + i, i, target)) return true;
}
}
}
return false;
} int main(void) { int caseNo = ;
while (true) {
totalValue = ;
flag = false;
for (int i = ; i < ; i++) {
cin >> stone[i];
totalValue += stone[i] * (i + );
}
if ((stone[] || stone[] || stone[] || stone[] || stone[] || stone[]) == ) {
break;
}
++caseNo;
//若价值和为奇数，一定不可分
if (totalValue % == ) {
cout<<"Collection #"<<caseNo<<':'<<endl;
cout<<"Can't be divided."<<endl<<endl;
continue;
}
if (dfs(, , totalValue / )) {
cout<<"Collection #"<<caseNo<<':'<<endl;
cout<<"Can be divided."<<endl<<endl;
continue;
}
else {
cout<<"Collection #"<<caseNo<<':'<<endl;
cout<<"Can't be divided."<<endl<<endl;
continue;
}
}
system("pause");
return ;
}