脚本宝典收集整理的这篇文章主要介绍了回溯法之子集和问题,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
问题描述:
子集和问题的一个实例为<S,M>。其中S={x1,x2,…,xn}是一个正整数的集合,M是一个正整数。找出S的所有子集S1,使得S1中所有元素的和为M。试设计一个解子集和问题的回溯法。
样例输入:
5 10 12 13 15 18
30
样例输出:
5 10 15
5 12 13
12 18
样例说明:
输入第一行是集合S,第二行是整数M;输出每一行代表一个解
#include <iostream>
using namespace std;
int s[100],n;
int m;
int flag[100];//标记被使用的元素,便于输出
int sum=0;//临时的子集和
void dfs(int t)
{
if(sum==m)
{
for(int i=0;i<n;i++)
{
if(flag[i])
cout<<s[i]<<" ";
}
cout<<endl;
}
else if(sum>m||t>=n)//剪枝函数
return;
else
{
flag[t]=1;
sum+=s[t];
dfs(t+1);
flag[t]=0;
sum-=s[t];
dfs(t+1);
}
}
int main()
{
int x,i=0;
while(cin>>x)
{
s[i++]=x;
if(cin.get()=='n')
break;
}
n=i;
cin>>m;
dfs(0);
return 0;
}
以上是脚本宝典为你收集整理的回溯法之子集和问题全部内容,希望文章能够帮你解决回溯法之子集和问题所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。