類型： 回溯， 迭代加深搜索， 減枝
原題：
An addition chain for n is an integer sequence with the following four properties:
a0 = 1
am = n
a0<a1<a2<...<am-1<am
For each k ( ) there exist two (not neccessarily different) integers i and j ( ) with ak =ai +aj
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.
樣例輸入：
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， 然後輸出一個元素個數最少的從1到n的序列（可能有多種方案，輸出其中一種即可）。
其中對於第k個數Ak， 它的值等於Ai+Aj( ) 。
分析與總結：
這一題是典型的迭代加深搜索+減枝的題目。
迭代加深的搜索（IDS，Iterative Deepening Search）：
迭代加深搜索，實質上就是限定下界的深度優先搜索。即首先允許深度優先搜索K層搜索樹，若沒有發現可行解，再將K+1後重復以上步驟搜索，直到搜索到可行解。
在迭代加深搜索的算法中，連續的深度優先搜索被引入，每一個深度約束逐次加1，直到搜索到目標為止。
迭代加深搜索算法就是仿廣度優先搜索的深度優先搜索。既能滿足深度優先搜索的線性存儲要求，又能保證發現一個最小深度的目標結點。
從實際應用來看，迭代加深搜索的效果比較好，並不比廣度優先搜索慢很多，但是空間復雜度卻與深度優先搜索相同，比廣度優先搜索小很多。
對於這一題，首先可以求出最少需要幾個元素可以達到n。按照貪心的策略，對於每個元素的值，都選擇讓它等於一個數的兩倍，即對於每個Ai = Ai-1 + Ai-1, 當Ai>=n時就跳出循環，得到最少元素個數。
然後從最少步數開始迭代加深搜索。 然後再用上一些減枝技巧即可。
[cpp]
// 深度迭代搜索+減枝 Time: UVa 0.012s POJ: 0MS
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,ans[100];
bool flag;
void dfs(int cur, int depth){
if(flag) return;
if(cur==depth){
if(ans[cur]==n) flag=true;
return ;
}
for(int i=0; i<=cur; ++i){
for(int j=i; j<=cur; ++j)if(ans[i]+ans[j] > ans[cur] && ans[i]+ans[j]<=n ){ // 這裡也進行減枝
// 下面這個減枝至關重要！！如果從當前一直往下都是選擇最大的策略還是不能達到n，跳過
bool ok = false;
int sum=ans[i]+ans[j];
for(int k=cur+2; k<=depth; ++k)
sum *= 2;
if(sum < n) continue;
ans[cur+1] = ans[i]+ans[j];
dfs(cur+1, depth);
if(flag)return;
}
}
}
int main(){
while(scanf("%d", &n),n){
memset(ans, 0, sizeof(ans));
ans[0] = 1;
flag = false;
// 計算出至少需要多少步
int m=1, depth=0;
while(m<n){
m *= 2;
depth++;
}
// 從最少步開始進行迭代加深搜索
while(true){
dfs(0, depth); www.2cto.com
if(flag) break;
depth++;
}
printf("%d", ans[0]);
for(int i=1; i<=depth; ++i)
printf(" %d", ans[i]);
printf("\n");
}
return 0;
}
