poj 1011 Sticks

Description

Input

Output

Sample Input

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

Sample Output

6
5

思路启发：

    越长的木棍对后面木棍的约束力越大，因此要把小木棍排序，按木棍长度从大到小搜索，这样就能在尽可能靠近根的地方剪枝。（剪枝一）

    如果当前木棍能恰好填满一根原始木棍，但因剩余的木棍无法组合出合法解而返回，那么让我们考虑接下来的两种策略，一是用更长的木棍来代替当前木棍，显然这样总长度会超过原始木棍的长度，违法。二是用更短的木棍组合来代替这根木棍，他们的总长恰好是当前木棍的长度，但是由于这些替代木棍在后面的搜索中无法得到合法解，当前木棍也不可能替代这些木棍组合出合法解。因为当前木棍的做的事这些替代木棍也能做到。所以，当出现加上某根木棍恰好能填满一根原始木棍，但由在后面的搜索中失败了，就不必考虑其他木棍了，直接退出当前的枚举。（剪枝二）

    显然最后一根木棍是不必搜索的，因为原始木棍长度是总木棍长度的约数。（算不上剪枝）

    考虑每根原始木棍的第一根木棍，如果当前枚举的木棍长度无法得出合法解，就不必考虑下一根木棍了，当前木棍一定是作为某根原始木棍的第一根木棍的，现在不行，以后也不可能得出合法解。也就是说每根原始木棍的第一根小木棍一定要成功，否则就返回。（剪枝四）

    剩下一个通用的剪枝就是跳过重复长度的木棍，当前木棍跟它后面木棍的无法得出合法解，后面跟它一样长度的木棍也不可能得到合法解，因为后面相同长度木棍能做到的，前面这根木棍也能做到。（剪枝五）

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define N 100
int a[N],mark[N],t,sum,n;
int cmp(const void*a,const void*b)
{
	return *(int *)a>*(int *)b?-1:1;      //数组从大到小排序
}
int find(int p,int rest,int s)
{
	int i;
	if(s==t)   //显然最后一根木棍是不必搜索的，因为原始木棍长度是总木棍长度的约数。
		return 1;
	for(i=p;i<n;i++)
		if(!mark[i]&&a[i]<=rest)          
		{
			mark[i]=1;
			if(a[i]==rest) 
			{
				if(find(0,t,s-a[i]))        
					return 1;
			}
			else if(find(i+1,rest-a[i],s-a[i]))
				return 1;
			mark[i]=0;              
			if(rest==t)          
				return 0;  
			if(a[i]==rest)      
				return 0;
			while(a[i]==a[i+1]) 
				i++;    
		}
	return 0;
}
int main()
{
	int i;
	while(scanf("%d",&n),n)
	{
		sum=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
		}
		qsort(a,n,sizeof(a[0]),cmp);
		t=a[0];
		memset(mark,0,sizeof(mark));
		while(sum%t!=0)
			t++;
		while(find(0,t,sum)==0)
		{
			t++;
			while(sum%t!=0)
				t++;
		}
		printf("%d\n",t);
	}
	return 0;
}

poj 1011 Sticks

原文：http://blog.csdn.net/u011721440/article/details/19631927