7-1 子集和问题--回溯法（算法设计与分析）-Toy模板网

这篇具有很好参考价值的文章主要介绍了7-1 子集和问题--回溯法（算法设计与分析）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

7-1 子集和问题

作者陈晓梅单位广东外语外贸大学

设集合S={x1,x2,…,xn}是一个正整数集合，c是一个正整数，子集和问题判定是否存在S的一个子集S1，使S1中的元素之和为c。试设计一个解子集和问题的回溯法，并输出利用回溯法在搜索树（按输入顺序建立）中找到的第一个解。

输入格式:

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

输出格式:

输出利用回溯法找到的第一个解，以空格分隔，最后一个输出的后面有空格。当问题无解时，输出“No Solution!”。

输入样例:

在这里给出一组输入。例如：
5 10
2 2 6 5 4
输出样例:

在这里给出相应的输出。例如：
2 2 6 

子集和问题

思路：（回溯法）根据已选元素之和加上当前元素加到最后一个元素来判断

代码如下：

#include<iostream>
using namespace std;

int n;
int c;
int final=0;  //当前元素加到最后一个元素 的总和
int sum=0;   //已选元素之和
int a[10000];   //原数组
bool b[10000];   //判断元素选不选

bool Backtrack(int t){
	if(sum==c) return true;  //已找到
	if(t>n) return false;    //未找到
	
	final-=a[t];   //先减去该元素
	
	if(sum+a[t]<=c){    //如果 已选元素之和 加上 该元素 小于等于c，则
		b[t]=true;    //选上该元素
		sum+=a[t];   //已选元素之和 加上 该元素
		if(Backtrack(t+1)) return true;   //下一个元素Backtrack成功 返回true
		sum-=a[t];    //否则 减回去
	}
	
	if(sum+final>=c){     //如果 已选元素之和 加上 当前元素加到最后一个元素的总和 大于等于c， 则
		b[t]=false;    //不选当前元素
		if(Backtrack(t+1)) return true;  //下一个元素Backtrack成功 返回true
	}
	
	final+=a[t];   //加回去
	return false;   //未找到
}

int main(){
	cin>>n>>c;
	for(int i=0;i<n;i++){
		cin>>a[i];
		final+=a[i];
	}
	if(!Backtrack(0))
	  cout<<"No Solution!"<<endl;
	else{
		for(int i=0;i<n;i++){
			if(b[i]) cout<<a[i]<<" ";  //如果该元素为ture，则输出
		}
	}
	return 0;
}

输入：

5 10

2 2 6 5 4

输出：

2 2 6文章来源地址https://www.toymoban.com/news/detail-756615.html

到了这里，关于7-1 子集和问题--回溯法（算法设计与分析）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！