UVA 529 - Addition Chains 剪枝+迭代深搜

题目大意：给出一个数字n，要求输出符合公式要求的最短的答案（对于第k个数，必需由前k-1个数选择其中两个进行相加得到，这两个数可以是同一个数，第一个数以给，为1）

解题思路：按最大策略求出最短的迭代次数，如果在当前迭代次数下，没有找到答案，就将迭代次数加1，再进行迭代，直到找到答案

剪枝1：如果前面的数的和不大于当前数的和，或者大于n，就没必要进行迭代了，因为存放答案是按升序排列的，如果符合的话，前面就会有记录

剪枝2：符合1的要求了，得到的数如果按最大策略进行迭代，即下一个数是前一个数的两倍，如果按最大策略迭代完了，还是小于n的话，那么该数就不符合，继续寻找下一个数

#include<cstdio>

bool flag;
int ans[100];
int deep,n;
//cur当前迭代的次数，ans中确定的下标的最大值，deep表示要迭代的次数，也表示要确定的下标的最大值
void dfs(int cur, int deep) {

	if(cur == deep) {
		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的话也不能进行迭代,剪枝1
					int sum = ans[i] + ans[j];
					//如果从当前往下一直迭代，最大策略的情况下还不符合要求的话，就继续寻找下一个值
					for(int k = cur+2 ; k<= deep; k++)
						sum = sum * 2;
					if(sum < n)
						continue;
					
					ans[cur+1] = ans[i] + ans[j];
					dfs(cur+1,deep);
					if(flag) return ;	
			}
}

int main() {
	
	while(scanf("%d",&n)!= EOF && n) {
		ans[0] = 1;
		flag = false;
		deep = 0;
		int m = ans[0];
		while(m < n) {
			m = m * 2;
			deep++;	
		}

		while(true) {
			dfs(0,deep);
			if(flag)
				break;	
			deep++;	
		}

		printf("%d",ans[0]);	
		for(int i = 1; i <= deep; i++) {
			printf(" %d",ans[i]);	
		}
			printf("n");		
	}
	return 0;
}

最后

以上就是糊涂曲奇为你收集整理的UVA 529 - Addition Chains 剪枝+迭代深搜的全部内容，希望文章能够帮你解决UVA 529 - Addition Chains 剪枝+迭代深搜所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。