小木棍(最优性剪枝、可行性剪枝)
一、问题描述
- 乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，已知每段的长都不超过 50 。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始最短木棍的可能长度
二、输入格式
- 第一行为一个整合 N，表示砍过以后的小木棍总数，其中 \(N\leq 60\)
- 第二行为 N 个用空格隔开的整数，表示 N 根小木棍的长度
三、输出格式
四、样例输入
9
5 2 1 5 2 1 5 2 1
五、样例输出
6
六、思路分析
- 利用搜索枚举所有可能出现的情况 every_len，从 1 开始，枚举到它们所有的和(最坏的情况，只有一根)，枚举的状态是当前木棍数 now，当前已获得木棍长度 now_len，当前要处理的序号 now_code，递归从 now_len 开始，以 now_len 是否为 0 为标志，如果为 0，则需要传入一个新的 now_len(判断下一个数)，如果不为 0，若等于 every_len，说明找到一组满足条件的数，传入一个新的 now，并将 now_len 置为 0，如果不等于 every_len，说明还未达到 every_len，那么需要加数字，再进行判断，通过 now_code 传递下标，如果下标没变，说明这个 every_len 不合适，退出递归，直至判断完所有 every_len。
七、剪枝分析
- 上下界剪枝——上界为所有小木棍的和，下界为最长的小木棍，即原木棍长度一定大于最长的木棍
- 优化搜索顺序——对原数据排序，避免重复情况
- 最优性剪枝——原木棍长度一定可以被所有木棍长度之和整除，不然无法拼出整数根
- 可行性剪枝 1——相同长度的木棍不需要搜索多次，因此有相同长度的木棍，就不用再次进入递归
- 可行性剪枝 2——找到结果后，立马返回上层递归处
- 可行性剪枝 3——搜索到的木棍组成的大于 every_len ，停止搜索
八、代码
#include<iostream>
#include<cstdlib>
#include <cstring>
#define MAX_N 64
using namespace std;
int n,sum_len,len[MAX_N+1],every_len,num;
bool used[MAX_N+1];
bool legal;
int compare(const void* e1,const void* e2)
{
return *(int *)e2-*(int *)e1;
}
void dfs(int now,int now_len,int now_code)
{
if(legal)
return;
if(now_len == every_len) //可行性剪枝 2
{
dfs(now+1,0,0);
return;
}
if(now == num)
{
legal = true;
return;
}
if(now_len == 0)
{
for(int i = 1; i <= n; i++)
if(!used[i])
{
used[i] = true;
dfs(now,len[i],i+1);
used[i] = false;
return;
}
}
int j=0;
for(int i = now_code;i <= n;i++)
{
if(now_len+len[i] <= every_len && !used[i] && (len[i] != len[j])) //可行性剪枝 3，可行性剪枝 1
{
j = i;
used[i] = true;
dfs(now,now_len+len[i],i+1);
used[i] = false;
}
}
return;
}
int main()
{
ios::sync_with_stdio(false);
while(cin >> n && n)
{
sum_len = 0;
for(int i = 1;i <= n; i++)
{
cin >> len[i];
sum_len += len[i];
}
qsort(len+1,n,sizeof(int),compare); //优化搜索顺序
memset(used,false,sizeof(bool));
for(every_len = len[1];every_len <= sum_len;every_len++) //上下界剪枝
if(sum_len % every_len == 0) //最优性剪枝
{
legal = false;
num = sum_len/every_len;
dfs(1,0,1);
if(legal)
break;
}
cout<<every_len<<endl;
}
return 0;
}