经典递归问题--木棍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

解题思路：不仅仅是单纯的递归，这个题目还涉及到一些特殊情况的判断，也就是剪枝操，否则就会超时。递归的整体思路是：在一堆木棍里面寻找备选答案的组合，成功找到一组后应该把用过的木棍排除在外继续重复这个过程。直到递归的出口：木棍被用完了并且此时的组合正好是备选答案。

// 木棍问题.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include<stdio.h>
#include<stdlib.h>

int a[100];
bool a_[100];
int n=0;

int cmp(const void *elem1,const void *elem2)  //qsort比较函数  
	{  
	    return *(int *)elem2 - *(int *)elem1;   //降序排列  
	} 


bool find_com(int ucnt,int temp,int ans)
{
	int j=0;
	
	if(ucnt==0&&temp==0)  
		return true;//木棍都用完了
	if(temp==0)
		temp=ans;
	for(j=0;j<n;j++)
	{     
		if(a_[j]==true)
			continue;
		if(a[j]>temp) 
			continue;
		a_[j]=true;//规模减小
		if(find_com(ucnt-1,temp-a[j],ans))
			return true;
		a_[j]=false;

		if(a[j]==temp||temp==ans) 
			break;//剪枝
	}
	return false;

}




int main()
{
	int sum=0;
	//freopen("in.txt","r",stdin);
	scanf("%d",&n);
	while(n!=0)
	{
		//memset(a,0,sizeof(a));
		//memset(a_,false,sizeof(a_));

		int i=0;
		int ucnt=n;
		sum=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
			a_[i]=false;
		}
		//sort(a,a+n,cmp);//从大到小排序 
		qsort(a,n,sizeof(int),cmp);  //对木棍进行排序  
		int len=a[0];
		for(i=len;i<=sum;i++)//从最大的木棍开始
		{
			if((sum%i!=0))
				continue;
			if(find_com(ucnt,0,i))//判断i是不是解
			{
				printf("%d\n",i);
				break;
			}
		}
	scanf("%d",&n);
	}

	return 0;
}

经典递归问题--木棍POJ 1011,布布扣,bubuko.com

经典递归问题--木棍POJ 1011

原文：http://blog.csdn.net/linsheng9731/article/details/23362841