加法链的搜索优化

65 阅读 0 评论 43 点赞

我是靠谱客的博主整齐皮卡丘，最近开发中收集的这篇文章主要介绍加法链的搜索优化，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

//搜索顺序优化，从后面搜索不需要进行迭代深度的调整，已经较优

#include "stdio.h"

int a[11],b[11];//数据规模是n在10000以内，所以2的10次够了，取11足够
int k,flag,n,s;

void DFS();

int main()
{

   int i;
   while(scanf("%d",&n),n)
   {
       flag=0;
       a[0]=1;
       k=0; s=10;
       DFS();
       printf("%d",b[0]);
       for(i=1;i<=s;i++)
           printf(" %d",b[i]);
       printf("n");
   }
   return 0;
}

void DFS()
{
   int i;
   if(a[k]==n)
   {
       if(k<s)
       {
           for(i=0;i<=k;i++)
               b[i]=a[i];
           s=k;
       }
       return ;
   }
   else if(k>=s || a[k]>n)
       return ;
   for( i=k; i>=0; --i )
   {
       k++;
       a[k]=a[k-1]+a[i];
       DFS();
       k--;
   }
}

//迭代优化

#include <iostream>
#include <cstring>
using namespace std;
int n,ans[100];
bool finish;
void dfs(int x,int deep){
if(finish) return ;
if(x==deep) { if(ans[x]==n)finish=1; return; }
for(int i=0;i<=x;i++){
for(int j=i;j<=x;j++) if(ans[i]+ans[j]>ans[x]&&ans[i]+ans[j]<=n){//剪枝
int sum=ans[i]+ans[j];
for(int k=x+2;k<=deep;k++) sum<<=1;//sum *= 2;当前为x; sum存于x+1;
if(sum<n) continue;//如果接下来一直是最大策略还是不能达到n，剪枝
ans[x+1]=ans[i]+ans[j];
dfs(x+1,deep);
if(finish) return ;
}
}
}
int main(){
while(scanf("%d",&n),n){
memset(ans,0,sizeof(ans));
ans[finish=0]=1;
int tmp=n,deep=0; while(tmp>>=1) deep++;//求出最大深度；
while(!finish) dfs(0,deep++);
cout<<ans[0];
for(int i=1;i<deep;i++) cout<<" "<<ans[i];
cout<<endl;
}return 0;
}