回溯法之子集和问题

2024-03-02 21:56| 来源: 网络整理| 查看: 265

问题描述

在这里插入图片描述找到数组中加和等于目标值的几个数字并输出(不可重复)。

题目分析

典型的回溯法，解空间为子集树。这道题与0-1背包问题非常相似，可以将其理解为有权重的0-1背包问题。只不过是把0-1背包问题中的1表示为具体数字大小，0依然是0，表示不在子集和中。所以这个问题的解空间也是一个子集树。回溯法：子集树的解空间。子集树的解空间框架我们已经很熟悉了：

void Backtrack(int t) { if(t > n) Output(x); else{ for(在所有选择中遍历) { x[t] = 遍历到的选择; if(满足约束条件且没有超过边界条件) Backtrack(t+1); } } }

我们就是在待选集合中遍历，选择不同的数字并向下遍历，当遍历到尽头的时候停止遍历，如果当前sum==目标值，我们就输出子集。如果没有遍历尽头，我们就采取上述的框架进行回溯。但是如果某个点不能加入到子集中，我们会判断下，剩余值+目前总和是否>=目标值，如果大于等于目标值，我们就可以继续向下遍历，因为下面有机会使得子集合等于目标值。这个题目中我们会子集随机生成不同的数据集，通过文件流的方式输入，计算结果和时间效率。

代码 #include #include #include using namespace std; ifstream infile("input50.txt",ios::in); ofstream outfile("output.txt",ios::app); int prime=0; int sum=0,m=0,n=0,r=0; int a[1010]={0}; //集合 int b[1010]={0}; //找到的一个解向量 void Solve(int k) { if(prime==1) return; if(k==n) { if(sum==m) //相等时输出一个解 { prime=1; for(int i=0;i sum+=a[k]; //假设a[k]在目标集合中 b[k]=a[k]; //将a[k]放到目标集合 Solve(k+1);//继续寻找下一个元素 sum-=a[k]; //如果刚才的元素不能到最后输出，那么会回到这，表示这个元素不在其中 b[k]=0; //将目标集合的这个元素清除 //剪枝操作，如果剩余元素+当前总和=m)//此时表示不用剪枝,有必要继续向下 Solve(k+1); r+=a[k];//回溯时,要将剩余值总和加回来 } } //这里把主要的函数当作参数传递给计算时间的函数,是一种很方便的方法 double testTime(void Solve(int),int a) { LARGE_INTEGER frequency;//时间对象 double dff,begin_,_end;//时钟频率，起始时间，结束时间，时间差 QueryPerformanceFrequency(&frequency);//获得时钟频率 dff=(double)frequency.QuadPart;//取得频率 QueryPerformanceCounter(&frequency); begin_=frequency.QuadPart;//获得初始值 Solve(a); QueryPerformanceCounter(&frequency); _end=frequency.QuadPart;//获得终止值 return (_end-begin_)/dff;//差值除以频率得到时间 } int main() { memset(b,0, sizeof(b)); infile>>n>>m; for(int i=0;i outfile

【本文地址】

公司简介

联系我们