首页 > 代码库 > search1011
search1011
题意：有一些 木棍，它们的长度相同。现在将木棍折断，最多折成64根。
编程求木棍可能的最小长度。
越长的木棍对后面木棍的约束力越大，因此要把小木棍排序，按木棍长度从大到小搜索，这样就能在尽可能靠近根的地方剪枝。（剪枝一）
如果当前木棍能恰好填满一根原始木棍（可能已经是第二层甚至第N层DFS了，此时原始木棍长度要小于最外层原始木棍长度），但因剩余的木棍无法组合出合法解而返回，那么后面的遍历方针是是用更短的木棍组合来代替这根木棍，他们的总长恰好是当前木棍的长度(直接用长的都无法最终成功，用了小的更不可能成功，因为小的、零碎的用途更多)，但因为当前木棍的做的事和这些替代木棍之和做的事一样，直接退出当前的枚举。（剪枝二）
显然最后一根木棍是不必搜索的
考虑每根原始木棍的第一根木棍，如果当前枚举的木棍长度无法得出合法解，就不必考虑下一根木棍了，当前木棍一定是作为某根原始木棍的第一根木棍的，现在不行，以后也不可能得出合法解。也就是说每根原始木棍的第一根小木棍一定要成功，否则就返回。（剪枝四）
剩下一个通用的剪枝就是跳过重复长度的木棍（剪枝五）
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int used[100],len[100],sum,n,Min,s[100];int find(int p,int rest,int trest){ int i; if (trest==Min) return 1; //剩余所有的小木棍之和恰好是需要凑成的MIN for (i=p;i<=n;i++) if (!used[i]&&len[i]<=rest)//这里必须要遍历，考虑某个组合木棍还缺少4，如果剩余的仅仅有3 2 2，//如果把3加上则永远得不到成功的，因为必须要用2+2. { used[i]=1; if (len[i]==rest) { if (find(1,Min,trest-len[i])) return 1; //本次组合成功，查看其余小木棍能否成功因此//从1开始return不仅仅跳出循环，还跳出整个函数 } else if (find(i+1,rest-len[i],trest-len[i])) return 1;//本次组合未完成，从更小的（i+1）开始搜索其余部分，使得和为rest used[i]=0;//不成功如果成功不会进行到这里，因为前面已经RETURN跳出整个函数 if (len[i]==rest) return 0;//剪纸2，跳出循环，不用再遍历了，这里的遍历即是用别的组合来得到rest if (rest==Min) return 0; //剪纸4，跳出循环，不用再遍历了 while (len[i+1]==len[i]) i++;//（剪枝五） } return 0;}bool cmp(int a,int b) {return a>b;}int main(){ int i; while (scanf("%d",&n)&&n!=0) { for (i=1;i<=n;i++) scanf("%d",&len[i]); memset(used,0,sizeof(used)); sort(len+1,len+n+1,cmp); sum=0; for (i=1;i<=n;i++) sum+=len[i]; Min=len[1]; while (sum%Min!=0) Min++; s[n+1]=0; while (find(1,Min,sum)==0) { Min++; while (sum%Min!=0) Min++; } printf("%d\n",Min); } return 0;
search1011
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。