问题描述：http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1011
主要想用回溯法的思想解决它。关键是要确定搜索的顺序。要提高算法的效率还要找到合适的剪枝。
// Sticks1.cpp : Defines the entry point for the console application.// http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1011// 首先将所有的小棒按从大到小的顺序排序// 搜索策略：// 每次用小棒组成原始棒，都要用到当前剩余的最长的小棒// 搜索每根原始棒的时候，组成它的每个小棒的长度由大到小排列，// 所以Search的时候有个startno，表示搜索下一个小棒的时候，从startno开始搜索#include "stdafx.h"#include <iostream>#include <algorithm>#include <functional>using namespace std;
short len[64];bool b[64];short n,poslen,sticks;
//stickno为要组装的第几根原始棒，startno为组装第stickno个原始棒的时候，从第startno个小棒开始查找，//leftlen表示组装第stickno个原始棒的时候，还缺多leftlen的长度bool Search(short stickno, short startno, short leftlen){ //搜索到最后一个原始棒，剩余的小棒的总长度必然等于原始棒的长度 if(stickno==sticks-1) return true;
//搜索第stickno个原始棒，如果第stickno个小棒还没使用，表明 //第stickno个小棒不能参与组成原始棒，则整个搜索失败 if( stickno>0 && !b[stickno-1] ) return false;
for(int i=startno; i<n; i++) { if(!b[i]) { //如果有连续的几根小棒长度相等，且前一个小棒不被使用，则当前小棒也不能使用，避免重复搜索 if( (i>0)&&(!b[i-1]) && (len[i-1]==len[i])) continue;
//正好组成一个原始棒 if(len[i]==leftlen) { b[i] = true; //搜索下一个原始棒，如果成功则返回true，如果失败，则回溯 if (Search(stickno+1,0,poslen)) return true; b[i] = false; } else if(len[i]<leftlen) { int j = n-1; while(b[j]) j--; if(len[i]+len[j]<=leftlen) { b[i] = true; if(Search(stickno,i+1,leftlen-len[i])) return true;//此处的第二个参数设为i+1非常关键，提高了搜索速度 b[i] = false; } } } }
return false;}
void main(){ short i,maxlen,totallen; cin>>n; while(n) { maxlen = totallen = 0;
for(i=0; i<n; i++) { cin>>len[i]; if(len[i]>50) len[i]=0; totallen += len[i]; if(len[i]>maxlen) maxlen = len[i]; }
//对每小段的大小按从大到小的顺序排序 sort(&len[0],&len[n],greater<int>()); //清除长度为0的棒 i=0; while((i<n)&&(len[i]>0)) i++; n = i;
for(poslen=maxlen; poslen<totallen; poslen++) { //棒的个数不为整数则改变poslen的大小再试 if(totallen%poslen) continue;
//将所有小段设为未选择 memset(b,0,n*sizeof(bool));
//为每根长度为poslen的stick找到各个小段，这些小段的和为poslen sticks = totallen / poslen; if(Search(0,0,poslen)) break; } cout<<poslen<<endl;
cin>>n; }}
