搜索算法——子集和问题

1.子集和问题

Description

子集和问题的一个实例为〈S,t〉。其中，S={  x1 ， x2 ，…，xn }是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得：
 

试设计一个解子集和问题的回溯法。
对于给定的正整数的集合S={  x1 ， x2 ，…，xn }和正整数c，计算S 的一个子集S1，使得：
 

Input

输入数据的第1 行有2 个正整数n 和c（n≤10000，c≤10000000），n 表示S 的大小，c是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。

Output

将子集和问题的解输出。当问题无解时，输出“No Solution!”。

Samples

Sample #1

Input 

5 10
2 2 6 5 4

Output 

2 2 6

2.代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int a[N],ans[N];
bool flag=0;
int n,c;
void Search(int x,int sum,int len)
{
	if(sum>c||flag==1) return ;
	if(sum==c) 
	{
		for(int i=0;i<len;i++)
		{
			if(i==len-1)
			{
				cout<<ans[i]<<endl;
			}
			else
			{
				cout<<ans[i]<<" ";
			}
		}
		flag=1;
		return ;
	}
	for(int i=x;i<n;i++)
	{
		if(sum+a[i]<=c)
		{
			ans[len]=a[i];
			Search(i+1,sum+a[i],len+1);
		}
	}
}
int main()
{
	cin>>n>>c;
	int sum1=0;
	for(int i=0;i<n;i++)
	{
	    cin>>a[i]; 
		sum1+=a[i];	
	}
	if(sum1<c) cout<<"No Solution!"<<endl;
	else Search(0,0,0);
	return 0;
}

3.代码解析

（1）全局变量：

 n 和 c 分别存储集合 S 的大小和目标值。
a[N] 用来存储集合 S 中的元素。
ans[N] 用来存储当前找到的子集。
flag 用来标记是否找到了一个解。

（2）Search 函数：

这是一个递归函数，用于回溯搜索子集。
x 参数表示当前搜索到的元素索引。
sum 参数表示当前子集的和。
len 参数表示当前子集的长度。
如果 sum 超过 c 或者已经找到解（flag 为 1），则返回。
如果 sum 等于 c，则打印当前子集并设置 flag 为 1。
否则，遍历集合 S 中的元素，尝试将每个元素加入到当前子集中，并递归搜索。

（3）main 函数：

读取输入的 n 和 c。
读取集合 S 中的元素，并计算总和 sum1。
如果总和 sum 小于 c，则输出“No Solution!”`，因为不可能找到满足条件的子集。
否则，调用 Search 函数从索引 0 开始搜索，初始 sum 为 0，len 为 0。

（4）代码中的 flag 变量：

flag 变量被用来标记是否找到了一个解。一旦找到解，就不再继续搜索，这可以提高效率。

（5）代码中的 ans 数组：

ans 数组被用来存储当前找到的子集。在 Search 函数中，每次找到一个元素可以加入子集时，就将其加入到 ans 中。

（6）代码中的 cout 语句：

当找到解时，代码使用 cout 打印当前子集。如果子集的和等于目标值 c，则打印子集中的元素。
（7）代码中的边界条件：
在 Search 函数中，有一个边界条件 if(sum + a[i] <= c)，这确保了不会超过目标值 c。
代码的效率：
（8）由于子集和问题是NP完全问题，这个回溯算法在最坏情况下的时间复杂度是指数级的，特别是当 n 很大时。
代码只输出找到的第一个解，如果存在多个解，它不会输出所有解。

4.拓展：

return ；

在C++中，一个函数是否有返回值取决于其声明的返回类型。以下是如何判断函数是否有返回值的方法：
（1） 返回类型声明：
   查看函数声明或定义时指定的返回类型。如果返回类型不是 void，那么函数必须返回相应类型的值。
（2）函数定义：
    在函数的定义中，如果函数的返回类型不是 void，那么在函数体中必须至少有一个 return 语句，后面跟着一个与返回类型相匹配的值。
（3） 编译器错误：
   如果函数声明了返回类型（不是 void），但在函数体中没有提供返回值，编译器会报错，提示缺少返回值。
（4）return 语句：
   在函数体中查找 return语句。如果所有的 return 语句都返回了一个值，那么函数有返回值。如果存在 return;（无值返回），则函数在这些点上不返回值，但仍然可能有其他 return语句返回值。
（5）void 返回类型：
   如果函数的返回类型是 void，那么函数不需要返回任何值，return ; 语句仅用于退出函数。
（6）代码审查：
   审查代码，确保每个可能的执行路径都有一个 return语句，特别是在条件语句（如 if、else、switch）中。

return 0；

在C++程序中，return 0; 通常用在 main 函数的末尾，表示程序正常退出并且没有错误。这个语句的作用是：
（1）返回状态码：return 语句将控制权从 main 函数返回给操作系统，并传递一个状态码。在这里，0是一个约定的状态码，表示程序成功执行完毕。
（2） 结束程序执行：return 语句会导致程序立即结束，不再执行 main 函数之后的任何代码。
（3）符合C++标准：在C++标准中，main 函数被定义为返回 int 类型。因此，使用 return 0; 符合这一标准，并且提供了一个明确的退出点。
（4） 程序成功的标志：在很多操作系统中，0 作为退出状态码是一个通用的约定，表示程序没有错误地完成了它的任务。