二进制优化，事实上是物体的分解问题。

就是比方一个物体有数量限制，比方是13，那么就须要把这个物体分解为1。 2， 4， 6

假设这个物体有数量为25，那么就分解为1， 2， 4。 8。 10

看出规律吗，就是分成2的倍数加上位数，比方6 = 13 - 1 - 2 - 4， 10 = 25 - 1 - 2 - 4 - 8。呵呵，为什么这么分解？

由于这样分解之后就能够组合成全部1到13的数。为25的时候能够组合成全部1到25的数啦。

就是这么一个分解物体。最后组合的问题。

不明确？

给多几个数字组合：

31分解 1, 2, 4, 8, 16

32分解1,2,4, 8, 16, 1

33分解1,2,4,8,16,2

如此分解的。

想通了，就和一般背包问题一样做法了。

#include <stdio.h>

#include <vector>

using std::vector;

const int SIZE = 7;

int N[SIZE];

bool findPartition()

{

	int sum = 0;

	for (int i = 1; i < SIZE; i++)

		sum += i * N[i];

	if (sum & 1) return false;

	int half = sum >> 1;

	vector<bool> part(half+1);

	part[0] = true;

	for (int i = 1; i < SIZE; i++)

	{

		int k = 1;

		for ( ; (k<<1) <= N[i]; k <<= 1)

		{//例:13分解为1,2,4,6能够组合为1到13个物品。故此考虑了全部情况了

			for (int j = half; j >= k*i; j--)

			{

				if (part[j-k*i]) part[j] = true;

			}

		}

		k = N[i] - k + 1;

		for (int j = half; j >= k*i; j--)

		{

			if (part[j-k*i]) part[j] = true;

		}

	}

	return part[half];

}

int main()

{

	int t = 1;

	while (true)

	{

		int val = 0;

		for (int i = 1; i < SIZE; i++)

		{

			scanf("%d", &N[i]);

			val += N[i];

		}

		if (!val) return 0;

		if (findPartition()) printf("Collection #%d:\nCan be divided.\n\n", t++);

		else printf("Collection #%d:\nCan't be divided.\n\n", t++);

	}

	return 0;

}