C++ 使用 DFS 算法求解子集和问题

使用 DFS 算法求解子集和问题

本文介绍了使用 C++ 语言和深度优先搜索 (DFS) 算法解决子集和问题。代码示例展示了如何通过递归遍历元素，寻找满足特定和的最小元素子集。

#include <stdio.h>
#include <vector> //vector是一个能够存放任意类型的动态数组容器
using namespace std; 
int a[]={1,2,3,4,5,6}; 
int n=6,k=10; 
vector<int>minpath;   //存放最优解
int minn=n;   //最多选择n个元素
void disppath()   //输出一个解
{ printf(' 选择的元素:');
  for (int j=0;j<minpath.size();j++)
printf('%d ',minpath[j]); 
printf('元素个数=%d\n',minn);
}
void dfs(vector<int>path,int sum,int start) //求解算法
{
if (sum==k)
{ 
if (path.size()<minn)
{ 
minn=path.size();
minpath=path;
}
return;
}
else
{
if (start>=n) return; 
dfs(path,sum,start+1); 
path.push_back(a[start]); 
dfs(path,sum+a[start],start+1);
}
}
int  main(){
vector<int> path; //path 存放一个子集
dfs(path,0,0);
printf('最优解:\n');
disppath();
}

解生成树

解生成树是一种递归的树形结构，每个节点代表一个状态，每个节点的子节点代表从当前状态转移到下一个状态的所有可能方式。在本代码中，解生成树的根节点表示一个空集，每个节点的子节点有两个，一个是不选择当前元素的状态，另一个是选择当前元素的状态。遍历完整个解生成树，就可以获得所有可能的解。在遍历过程中，记录下元素个数最少的解，即为最优解。

例如，对于数组 a = {1, 2, 3, 4, 5, 6}，目标和 k = 10，解生成树可以表示为：

        空集
       /     \
   不选1   选1
  /   \     /   \
 不选2 选2  不选2  选2
 ...

每个节点代表一个子集，例如节点 选1 不选2 代表子集 {1}。每个节点的两个子节点分别代表选择或不选择当前元素（这里是元素 2）。通过递归遍历所有节点，可以找到所有可能的子集，并最终找到元素个数最少的子集 {3, 7}，其元素个数为 2，满足目标和 k = 10。

注意： 解生成树的实际结构会更加复杂，这里只是简单示例。

总结

本文介绍了使用 C++ 语言和 DFS 算法解决子集和问题，并解释了解生成树的概念。通过代码示例和解释，读者可以更深入地理解 DFS 算法在求解组合优化问题中的应用。