POJ1011 Sticks 深度优先搜索+剪枝

Sticks

Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output

The output should contains the smallest possible length of original sticks, one per line.

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

题意：将n跟不同长度的小棍拼接成若干跟长度相等的长棍，问能拼成的最短长度是多少。

分析：首先把木棍按长度降序排列（为了进行贪心选择），并计算总长度。从最长的小棍作为拼成的长棍长度aim开始搜索（剪枝1），若总长度能整除aim，则该方案有可能完成拼凑，否则增加aim大小，最坏的情况所有小棍拼在一起 aim=sum（若aim>sum/2则aim一定为sum）。深度优先搜索dfs，每选择一个木棒进行判断，若能拼成aim，再对其后的木棍进行递归搜索，若能匹配成功，则标记为用过，返回true；若不能匹配成功，说明该方案不可行，取消标记退出当前搜索（剪枝2）。每根要组合的新木棍的第一根最长的木棍一定要成功，否则该木棍之后也无法使用（剪枝3）。当前木棍长度len和后面木棍无法拼出时，跳过重复长度的木棍（剪枝4）。

 

#include<iostream>
#include<algorithm>

using namespace std;

const int maxn = 65;
int used[maxn],sticks[maxn];
int N,sum,aim,num;
 
bool cmp(int a, int b)
{
	return a > b;
}

bool dfs(int Stick, int len, int pos)
{//Stick表示当前组合好的棍子数，len表示正在组合的棍子已有的长度，pos表示搜索到第几根

	if (Stick+1 == num) return true;    //只剩最后一根不需再搜索一定成功

	for (int i = pos; i < N; i++)
	{
		if (used[i]) continue;
		if (len + sticks[i] == aim)    //正好组合成需要的长度
		{
			used[i] = true;            //标记当前木棍已使用
			if (dfs(Stick + 1, 0, 0))
				return true;
			used[i] = false;         //后面的木棍不能拼成功，标记取消
			return false;            //剪枝2
		}
		if (len + sticks[i] < aim)    //长度不够
		{
			used[i] = true;
			if (dfs(Stick, len + sticks[i], i + 1))
				return true;
			used[i] = false;
			if (len == 0) return false;  //第一根最长的小木棍不能拼成功则退出搜索，剪枝3
			while (sticks[i] == sticks[i + 1]) i++; //跳过重复长度木棍，剪枝4
		}
	}
	return false;
}
int main()
{
	while (cin >> N,N != 0)
	{
		sum = 0;
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &sticks[i]);
			sum += sticks[i];
		}
		sort(sticks, sticks + N, cmp);//降序排列
		for (aim = sticks[0]; aim <= sum; aim++)    //从最长的木棍长度开始搜索
		{
			if (sum%aim == 0)
			{
				num = sum / aim;
				memset(used, false, sizeof(used)); //初始化
				if (dfs(0, 0, 0))
				{
					cout << aim << endl;
					break;
				}
			}
		}
	}
	return 0;
}