DFS + 剪枝 —— POJ 1011

对应POJ题目：点击打开链接

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

POJ 2362 的加强版

题意：给一个数n， 然后给出n个数，每个数代表一根木棍长度，求这n根木棍恰好可以组成k根长度都为len的木棍。求len的最小值。

思路：搜索枚举 + 剪枝。

1、降序排序。

2、需要组成的长度len必须为总长sum的公约数。

3、枚举区间：最大木棍长度 ～ 总木棍长度。

4、在尝试组成一根长为len的木棍时，从第一根子木棍开始，如果失败了，那这根子木棍在后面肯定也用不上，所以直接返回失败。

5、在尝试组成一根长为len的木棍时，如进行到 11     8     ...   若 8  失败了，如果后面的还是8，肯定也不会成功，那直接跳过。

6、如果需要组k根长为len的木棍，那完成k-1次匹配后应该就可以了的，最后一次应该也可以匹配。不过提交却是TLE，可能是我考虑欠妥。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define M 70
using namespace std;
int a[M];
int vis[M];
int n;

int Dfs(int cnt, int beg, int t, int key_t, int sum, int key_len)
{
	if(sum == key_len){ //组成一根长为key_len的棍子
		t++;
		if(t == key_t) return 1; //棍子数为sum / key_len，成功。按道理这里改为 t == key_t - 1 似乎也是正确的，提交却是TLE
		sum = 0;
		for(beg=0; beg<n; beg++) //beg为下一根棍子的起始位置下标
			if(!vis[beg]) break;
		cnt = beg;
	}
	int i, flag = 0;
	for(i=cnt; i<n; i++){
		if(sum + a[i] <= key_len && !vis[i]){
			vis[i] = 1;
			sum += a[i];
			flag = Dfs(i+1, beg, t, key_t, sum, key_len);
			if(1 == flag) return 1;
			sum -= a[i];
			vis[i] = 0;
			while(a[i] == a[i+1]) i++;
		}
		if(!vis[beg]) return 0;
	}
	return 0;
}

bool cmp(int a, int b)
{
	return a > b;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	while(~scanf("%d", &n), n)
	{
		memset(vis, 0, sizeof(vis));
		int i;
		int sum = 0;
		for(i=0; i<n; i++){
			scanf("%d", &a[i]);
			sum += a[i];
		}
		sort(a, a+n, cmp);
		int ans, key_len;
		int ok = 0;
		for(ans=a[0]; ans<= sum; ans++){
			if(sum % ans) continue;
			key_len = sum / ans;
			ok = Dfs(0, 0, 0, key_len, 0, ans);
			if(ok) break;
		}
		printf("%d\n", ans);
	}
	return 0;
}

DFS + 剪枝 —— POJ 1011

原文：http://blog.csdn.net/u013351484/article/details/44538415