poj1011-Sticks-(DFS+剪枝)

发布于 2019-07-30  724 次阅读


问题传送门:

题意:

给你一个n个数的数组,最多50个吧。把这n个数分成若干组,使每组的和相等
怎样分组使这个和最小,输出这个和。

分析:

把n个数分成和相等的若干组,那么这个和ans:
最小可能是这个数组中的最大值 N,
最大可能是所有数的和 sum。
所以可以 从小到大 对每一个可能的和进行DFS,如果遇到可以满足的答案,break。
看起来思路很简单,但是TLE了无数次。。。。
这一题若要用DFS写需要多次剪枝操作
  1. 当N > S/2 时, 不需要再继续搜索了,答案就是 S。
  2. 只需要对 S的约数 进行深搜,因为每一组的和都是相等的。
  3. 如果a[i+1] == a[i] , 当a[i] 搜索失败的时候,a[i+1]一定失败,i++。
  4. 从大到小排序,方便剪枝。
  5. 最难想的一个重要剪枝,如果第 i 组的最大的数在匹配过程中失败,那么直接返回第i-1组重新匹配。因为第 i 组的组合一定是包含剩余的那数中最大的那个数。

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;

const int MAXN = 100;

int maxn, n;
int a[MAXN];
int vis[MAXN], f, S;

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

void clean(int n)
{
	for (int i = 0; i < n; i++)
		vis[i] = 0;
}

void DFS(int sum, int cnt,  int p)
{
	if (f || cnt == n) return ;
	for (int i = p; i < n; i++)
	{
		if (vis[i] || sum + a[i] > maxn) 		
			continue;

		vis[i] = 1;
		if (sum + a[i] < maxn)		
			DFS(sum + a[i], cnt+1, i+1);
		else if (sum + a[i] == maxn) {
			if (cnt != n-1)
				DFS(0, cnt+1, 0);	
			else if (cnt == n-1) {
				f = 1;
				printf("%d\n",maxn);
				return ;
			}
		}
		vis[i] = 0;
		if(f || sum == 0) 
			return ;
		while (i+1 < n && a[i+1] == a[i])
			i++;
	}
}
int main()
{
	while (scanf("%d",&n)!=EOF && n)
	{
		S = 0, f = 0;
		int N = -1, j;
		for (int i = 0; i < n; i++)
		{
			scanf("%d",&a[i]);
			S += a[i];
			N = max(a[i], N);
		}
		sort(a,a+n,cmp);
		for (j = N; j <= S/2; j++)
		{
			if(S%j == 0)
			{
				clean(n);
				maxn = j;
				DFS(0, 0,  0);
				if (f) break;
			}	
		}
		if (j > S/2)
			printf("%d\n",S);
	}
	return 0;
}

Simple And Clear