Description
An addition chain for n is an integer sequence with the following four properties:
You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable.
For example, <1,2,3,5> and <1,2,4,5> are both valid solutions when you are asked for an addition chain for 5.
Hint: The problem is a little time-critical, so use proper break conditions where necessary to reduce the search space.
5 7 12 15 77 0
1 2 4 5 1 2 4 6 7 1 2 4 8 12 1 2 4 5 10 15 1 2 4 8 9 17 34 68 77
大致题意：
给你个n,找从 0 到 n 的最短序列，序列满足 每一个 a[k] 都存在a[i]+a[j]=a[k]，如果有很多，找到一个就够了。
解题思路：
用迭代加深搜索实现，需要注意很多地方剪枝。
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 int n,ans[100]; 5 bool finish; 6 void dfs(int x,int deep){ 7 if(finish) return ; 8 if(x==deep) { if(ans[x]==n)finish=1; return; } 9 for(int i=0;i<=x;i++){ 10 for(int j=i;j<=x;j++) if(ans[i]+ans[j]>ans[x]&&ans[i]+ans[j]<=n){//剪枝 11 int sum=ans[i]+ans[j]; 12 for(int k=x+2;k<=deep;k++) sum<<=1;//sum *= 2;当前为x; sum存于x+1; 13 if(sum<n) continue;//如果接下来一直是最大策略还是不能达到n，剪枝 14 ans[x+1]=ans[i]+ans[j]; 15 dfs(x+1,deep); 16 if(finish) return ; 17 } 18 } 19 } 20 int main(){ 21 while(scanf("%d",&n),n){ 22 memset(ans,0,sizeof(ans)); 23 ans[finish=0]=1; 24 int tmp=n,deep=0; while(tmp>>=1) deep++;//求出最大深度； 25 while(!finish) dfs(0,deep++); 26 cout<<ans[0]; 27 for(int i=1;i<deep;i++) cout<<" "<<ans[i]; 28 cout<<endl; 29 }return 0; 30 }
UVA 529 - Addition Chains，迭代加深搜索+剪枝
原文：http://www.cnblogs.com/nicetomeetu/p/5159002.html