HDU1059_Dividing_多重背包

题目大意：         给你6个石子，石子的价值分别从1->t;6,然后输入各个石子的数量。之后要你判断石子能否分成两堆，使两堆石子的价值一样。想了好久，最后觉得才发现可以用多重背包做。 解题思路： 首先这6种石子不是无数个的，而且石子有价值，可以假设石子的体积都一样，反正题目都木有要求体积嘛。 一开始先算出石子的总价值，然后判断总价值的奇偶性，如果是奇数，肯定分不了，偶数的话就多重背包下。以石子的总价值的一半作为背包。初始化为负无穷，如果最后h_tal是总价值的一半，dp[h_tal]如果有数量的话，那么就证明这个价值可以达到，意思就是可以取石子取出价值为总价值的一半，那么就满足了题意要求的平均分为一半。 ok,总的思路就是这样了，思路相当的清晰啊，不过这样做下去，直接就TLE了，因为这个总价值最多是20000*6，这可是120000/2啊，然后3个for循环，最坏的复杂度就是6*120000/2*20000.不超时才怪。 其实做个简单的处理就可以了，把各种石子的数量模10就行了，因为一种石子超过10，比如12，那么前面10个是肯定可以均分掉的，所以就不考虑它了，直接考虑2就行了。。 代码：

#include
#define max(x,y) x>y? x:y
const int inf=0x7fffffff;
using namespace std;
int dp[120005];
int main(void)
{
	int num[7],cas_c=1;
	while(cin>>num[1]>>num[2]>>num[3]>>num[4]>>num[5]>>num[6])
	{
		if(!num[1] && !num[2] && !num[3] && !num[4] && !num[5] && !num[6])
			exit (0);
		cout<<"Collection #"<=i;k--)
				{
					dp[k]=max(dp[k],dp[k-i]+1);
				}

		//cout<0)
			cout<<"Can be divided."<