题意:
给你一个n个数的数组,最多50个吧。把这n个数分成若干组,使每组的和相等
怎样分组使这个和最小,输出这个和。
分析:
把n个数分成和相等的若干组,那么这个和ans:
最小可能是这个数组中的最大值 N,
最大可能是所有数的和 sum。
所以可以 从小到大 对每一个可能的和进行DFS,如果遇到可以满足的答案,break。
看起来思路很简单,但是TLE了无数次。。。。
这一题若要用DFS写需要多次剪枝操作
- 当N > S/2 时, 不需要再继续搜索了,答案就是 S。
- 只需要对 S的约数 进行深搜,因为每一组的和都是相等的。
- 如果a[i+1] == a[i] , 当a[i] 搜索失败的时候,a[i+1]一定失败,i++。
- 从大到小排序,方便剪枝。
- 最难想的一个重要剪枝,如果第 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;
}
Comments | NOTHING