把總長度求出來，然后用和背包問題類似的dp算法求是否可以達到這個總長度的一半，但是超時了。
找到一個優(yōu)化方案，結果0ms就過了，orz
http://162.105.81.202/course/problemSolving/dividingProve.doc
以下論證均轉(zhuǎn)自這篇文章。
結論 對于任意一種珠寶的個數(shù)n，如果n>=8, 可以將n改寫為 11（n為奇數(shù)） 或 12（n為偶數(shù)）。
證明：
對于任意一組數(shù)，6的個數(shù)為n(n>=8)
一、如果可以分成兩堆，我們可以分成兩種情況：
1.
兩堆里都有6，那么我們可知：把n改為n-2，仍然可分。
(兩堆各減一個6)
2. 只有一堆里有6，設為左邊，那么左邊的總和不小于6*8=48。
我們觀察，5*6=6*5 ，4*3=6*2 ， 3*2=6 ， 2*3=6 ， 1*6=6
而 5*5 + 4*2 + 3*1 + 2*2 + 1*5 = 25 + 8 + 3 + 4 + 5 = 45 < 48
由抽屜原理右邊必然存在
(多于5個的5 或者 多于2個的4 或者 多于1個的3
或者 多于2個的2 或者 多于5個的1)
即右邊至少存在一組數(shù)的和等于若干個6，比如右邊有3個4，這樣把左邊的2個6與右邊的3個4交換，則又出現(xiàn)左右都有6的情況。 根據(jù)1，我們還是可以把n改為n-2且可分的狀態(tài)不變。
綜合1，2。我們可以看出只要原來n的個數(shù)=8,我們就可以把它改為n-2，這樣操作一直進行到n<8。我們可以得出結論，對于大于等于8的偶數(shù)，可以換成6。
對于大于8的奇數(shù)，可以換成7。換完之后仍然可分。
二、如果不能分成兩堆：
顯然改為n-2時同樣也不能分，那么對于大于等于8的偶數(shù)，可以換成6；對于大于8的奇數(shù)，可以換成7。換完之后仍然不可分。
綜合一、二，我們得出結論把不小于8的偶數(shù)改為8，大于8的奇數(shù)改為7，原來可分與否的性質(zhì)不會改變。
以上是對6的討論，同樣的方法可以推出
5的個數(shù) 6*4 + 4*4 + 3*4 + 2*4 + 1*4 = 64 < 5*13
即5的個數(shù)多于12時，偶數(shù)換為12，奇數(shù)換為11
4的個數(shù) 6*1 + 5*3 + 3*3 + 2*1 + 1*3 = 35 < 4*9
即4的個數(shù)多于8時，偶數(shù)換為8，奇數(shù)換為7
3的個數(shù) 5*2 + 4*2 + 2*2 + 1*2 = 24 < 3*9
即3的個數(shù)多于8時，偶數(shù)換為8，奇數(shù)換為7
2的個數(shù) 5*1 + 3*1 + 1*1 = 9 < 2*5
即2的個數(shù)多于4時，偶數(shù)換為4，奇數(shù)換為3
1的個數(shù) 多于5則必然可分(在總數(shù)是偶數(shù)的前提下)
綜上所述,
對于任意一種珠寶的個數(shù)n，如果n>=8, 可以將n改寫為 11（n為奇數(shù)） 或 12（n為偶數(shù)）。
進一步分析：
對每個數(shù)（1-6），以上只是粗略的估計，可以進一步減少其最大有效取值，例如，
對于6，5*5 + 4*2 + 3*1 + 2*2 + 1*5 = 25 + 8 + 3 + 4 + 5 = 45
就有4和2不能同時出現(xiàn)，5和1不能同時出現(xiàn)，3個5和1個3不能同時出現(xiàn)，4個5不能和1個4同時出現(xiàn)等等，所以組合不出6的整數(shù)倍的情況的總價值至多為25，所以當6的個數(shù)大于6時，奇數(shù)可改為5，偶數(shù)可改為6。
1-5 也有類似情況。
為了得出精確值，下面先我們討論這樣一個數(shù)論命題。
命題：
可重復的從自然數(shù)集中取出n個數(shù)（n>=2)，其中必有若干個數(shù)之和能被n整除。
證明：設取出的n個自然數(shù)為a1,a2,a3,.....an
考慮這樣的n+1個數(shù) 0, a1, a1+a2 , a1+a2+a3 , ...... , a1+a2+a3+...+an， 由于自然數(shù)模n的剩余類有n個，所以以上n+1個數(shù)中必有兩個同余。 這兩個數(shù)的差必被n整除，而且這兩個數(shù)的差就是原來的n個數(shù)中的一些數(shù)的和。
這就證明了命題。
由以上命題
對于6而言，我們至多從{1，2，3，4，5}中可重復的找出5個數(shù)使它們不能組合成6的倍數(shù)。
所以這些數(shù)的和小于等于5*5=25
對于5而言，我們至多從{1，2，3，4，6}中可重復的找出4個數(shù)使它們不能組合成5的倍數(shù)。
所以這些數(shù)的和小于等于6*4=24
對于4而言，我們至多從{1，2，3，5，6}中可重復的找出3個數(shù)使它們不能組合成4的倍數(shù)。
所以這些數(shù)的和小于等于3*6=18 ， 然而，兩個6就是4的倍數(shù)， 所以最多有一個6
此時不能有兩個5（2*5+6=16是4的倍數(shù)）， 最多才6 + 5 + 3 = 14 < 3*5 =15
所以這些數(shù)的和小于等于3*5=15
對于3而言，我們至多從{1，2，4，5，6}中可重復的找出2個數(shù)使它們不能組合成3的倍數(shù)。
所以這些數(shù)的和小于等于2*5=10
（6就是3的倍數(shù)，所以不能取6）
對于2而言，我們至多從{1，3，4，5，6}中可重復的找出1個數(shù)使它們不能組合成6的倍數(shù)。
所以這些數(shù)的和小于等于1*5=5
考慮到 4*6 < 25 < 5*6 , 我們可以算出6的最大有效個數(shù)為5 。
考慮到 4*5 < 24 < 5*5 , 我們可以算出5的最大有效個數(shù)為5 。但是其實應該修正為6， 如果遇到如下特殊情況，左邊5個6，右邊6個5。此時雖然左右可以交換，但是交換后仍然只有一邊有5，與（一、2）中討論情況不符。
考慮到 3*4 < 15 < 4*4 , 我們可以算出5的最大有效個數(shù)為4 。但是其實應該修正為5， 如果遇到如下特殊情況，左邊4個5，右邊5個4。此時雖然左右可以交換，但是交換后仍然只有一邊有4，與（一、2）中討論情況不符。
考慮到 3*3 < 10 < 4*3 , 我們可以算出5的最大有效個數(shù)為4 。但是其實應該修正為5， 如果遇到如下特殊情況，左邊3個5，右邊5個3。此時雖然左右可以交換，但是交換后仍然只有一邊有3，與（一、2）中討論情況不符。
考慮到 2*2 < 5 < 3*2 , 我們可以算出5的最大有效個數(shù)為3 。 但是其實應該修正為4，如果遇到如下特殊情況，左邊1個3和1個5，右邊4個2。此時雖然左右可以交換，但是交換后仍然只有一邊有2，與（一、2）中討論情況不符。
我們得出最后的精確結論：
奇數(shù)改為 偶數(shù)改為
6的個數(shù)大于5 5 4
5的個數(shù)大于6 5 6
4的個數(shù)大于5 5 4
3的個數(shù)大于5 5 4
2的個數(shù)大于4 3 4
優(yōu)化后的代碼：
#include <iostream>
using namespace std;
long n[6];
long sum;
const long MAX_N = 60000;
int dividable()
{
int f[MAX_N];
for (int i = 0; i <= sum; i++)
f[i] = 0;
f[0] = 1;
for (int i = 0; i < 6; i++)
{
for (int j = 1; j <= n[i]; j++)
{
int base = j * (i + 1);
if (base > sum) break;
for (int k = sum - (i+1); k >= base - i - 1; k--)
if (f[k])
f[k + i + 1] = 1;
if (f[sum]) return 1;
}
}
return f[sum];
}
int main()
{
long cases = 0;
while (true)
{
sum = 0;
for (long i = 0; i < 6; i++)
{
cin >> n[i];
}
if (n[5] > 5) n[5] = 4 + n[5] % 2;
if (n[4] > 6) n[4] = 6 - n[4] % 2;
if (n[3] > 5) n[3] = 4 + n[3] % 2;
if (n[2] > 5) n[2] = 4 + n[2] % 2;
if (n[1] > 4) n[1] = 4 - n[1] % 2;
for (long i = 0; i < 6; i++)
{
sum += n[i] * (i + 1);
}
if (sum == 0)
break;
cases++;
cout << "Collection #" << cases << ":\n";
if (sum % 2 != 0)
{
cout << "Can't be divided.\n\n";
continue;
}
sum /= 2;
if (dividable())
cout << "Can be divided.\n";
else
cout << "Can't be divided.\n";
cout << endl;
}
return 0;
}