递归与分治法

水深无声 2022-12-03 13:27 200阅读 0赞

将问题分解，通过求解局部性的小问题来解开与原本的问题。这种技巧称为分治法，我们在很多算法中都能看到。这个算法的步骤如下：  
1.将问题"分解“成局部问题  
2.递归地求解局部问题  
3.将局部问题地解”整合“，解决原问题

## 穷举搜索 ##

例题：  
现有长度为n地数列A和整数m。请编写一个程序，判断A中任意几个元素相加是否能够得到m。A中每个元素中能使用1次.  
数列A以及用作问题的q个m，由外界输入，请对每个问题输出yes或no  
输入：第1行输入n，第2行输入代表A的n个整数，第3行输入q，第4行输入q个整数m。  
输出：输出各问题的答案，如果A中元素相加能得到mi则回答yes，反之回答no  
限制：  
n<=20  
q<=200  
1<=A的元素<=2000  
1<=mi<=2000

#include<iostream>
    #define MAXN 2000
    using namespace std;
    int n,A[MAXN];
    bool solve(int i,int m){
        
    	if(m == 0) return true;
    	if(i == n) return false;
    	return (solve(i+1,m) || solve(i+1,m-A[i]));
    }
    int main(){
        
    	int m,temp;
    	cin>>n;
    	for(int i = 0;i < n;i++)
    		cin>>A[i];
    	cin>>m;
    	for(int i = 0;i < m;i++){
        
    		cin>>temp;
    		if(solve(0,temp))	cout<<"yes"<<endl;
    		else cout<<"no"<<endl;
    	}
    	return 0;
    }

**讲解**  
设solve(i,m)为”用第i个元素后面的元素能得出m时返回true“的函数，**这样一来solve(i,m)就可以分解为solve(i+1,m)和solve(i+1,m-A\[i\])这两个更小的局部问题**。这里减去A\[i\]表示”使用第i个元素“。我们只要将其递归，就可以解开原问题solve(0,m)。  
检查所有组合需要在递归函数中重复调用两个递归函数，算法复杂度为O(2^n)，**因此不适用于n较大的问题**。