poj1014 Dividing题解

原题：http://acm.pku.edu.cn/JudgeOnline/problem?id=1014

网上很多人说直接采用dp就可以了，但是我觉得不用那么复杂，用贪心算法+回溯+剪枝就可以了，而且特快，运行时间为0.

1.首先，将所有石子价值先加，如果sum为奇数，则返回false.

2.然后，采用贪心策略在石子中选择价值和为sum/2的组合，如果组合成功，返回true,否则false.

a).既然贪心，那当然首先选价值为6的石子，在不大于sum/2的前提下，尽量多选，假设数量为count。然后是价值为5，4，3，。。。

b).所谓回溯，就是当以上不能成功组合时，将count--，既少选一个，然后又是5，4，3，。。。

c).如果仅仅采用以上的步骤，最终答案肯定是正确的，但是肯定也会超时。因为某一价值的石子最大数量为20000，如果count--,得遍历多少啊。所以我们还要采用剪枝算法。

以第一步选择价值为6的石子为例，如果接下去的选择价值为5的石子的数量超过6个，则我们可以用5个价值为6的石子替代；同样，如果再接下去的选择价值为4的石子的个子超过3个，我们也可以用2个价值为6的石子替代，依此类推。于是我们可以得到，在有足够的价值为6的石子的前提下，设选择6的个数为count，那么必须有（sum/2 - count*6)<=(5*5+4*2+3+2*2+5）= 45.也就是回溯时count减小到一定数量不满足以上不等式时就停止，这样将剪去大部分的无用的搜索。当然，接下去的选择5，4，3，。。。都如此。

Source Code

Problem: 1014  User: hhh08 
Memory: 712K  Time: 0MS 
Language: G++  Result: Accepted 

Source Code 
#include<iostream>
#include<vector>
#include<string>
using namespace std;

string status[2] = {"Can't","Can"};
int gcm[6] = { 0,1,6,14,40,45};
int mableNum[6];

int MinNum(int a, int b)
{
	return a>b?b:a;
}

bool Dfs(int step,int restVal)
{
	if(restVal==0 && step>=-1)
		return true;

	if(step==-1)
		return false;

	int num = restVal/(step+1);
	num = MinNum(mableNum[step],num);

	int count = num;
	restVal -= count*(step+1);

	while(count>=0)
	{
		if(Dfs(step-1,restVal))
		{
			return true;
		}
		count--;
		restVal += step+1;
		if(restVal>gcm[step])
			return false;
	}
	return false;
}


int main()
{
	vector<int > vstatus;
	int sumVal;
	while(1)
	{
		sumVal = 0;
		for(int i=0;i<6;i++)
		{
			cin>>mableNum[i];
			sumVal += mableNum[i]*(i+1);
		}
		if(sumVal==0)
		{
			break;
		}
		if(sumVal&1)
		{
			vstatus.push_back(0);
			continue;
		}

		if(Dfs(5,sumVal/2))
		{
			vstatus.push_back(1);
		}
		else
		{
			vstatus.push_back(0);
		}
	}

	for(int i=0;i<vstatus.size();i++)
	{
		cout<<"Collection #"<<i+1<<":/n"<<status[vstatus[i]]<<" be divided./n"<<endl;
	}

	return 0;
}