n,0,0))
{
cout<<InitLen<<endl;
flag=true;
break;
}
}
if(!flag)
cout<<sumlen<<endl;
delete stick;
delete visit;
}
return 0;
}
bool dfs(int* stick,bool* visit,int len,int InitLen,int s,int num)
{
if(num==n)
return true;
int sample=-1;
for(int i=s;i<n;i++)
{
if(visit[i] || stick[i]==sample)
continue; // 剪枝（2）
visit[i]=true;
if(len+stick[i]<InitLen)
{
if(dfs(stick,visit,len+stick[i],InitLen,i,num+1))
return true;
else
sample=stick[i];
}
else if(len+stick[i]==InitLen)
{
if(dfs(stick,visit,0,InitLen,0,num+1))
return true;
else
sample=stick[i];
}
visit[i]=false;
if(len==0) // 剪枝（3）
break;
}
return false;
}
2.最优性剪枝
最优性剪枝，又称为上下界剪枝，是一种重要的剪枝策略。它记录当前得到的最优值，如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯。
对于求最优解的一类问题