[讨论]递归的回溯算法(求子集问题)

CHLOE

首先向编程中国的各位同仁朋友们问声好.

我第一次来此论坛发贴,希望以后能和你们多多交流

下面开门见山

说出我的问题,望各位都给出意见

W[ ] = {1,2,3,4,5,6,7,8,9,10},求出它的子集满足元素之和为 15 .这是初步的

进一步延伸,长度为n的数组W[n]. 求出所有子集满足元素之和为M.

希望各自给出自己的看法.

紫禁之颠

哈哈.今天晚上在这里等.

顺便自己在用VC调试程序

幸福乐园

这道题很好玩的啦，哈哈，思考中。。。

停淼心泪

有点意思！

阳光aiq浪子

#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> Set;
typedef vector<vector<int> > ResSet;
void getSub(Set& a, ResSet& res, int i, Set b,int filter=15);
void main()
{
Set w;
ResSet res;
for(int i = 0; i<10; i++){
w.push_back(i+1);
}
Set b;
getSub(w, res, 0, b);
cout<<res.size()<<endl;
for(unsigned i = 0; i< res.size(); i++)
{
Set b = res[i];
for(unsigned j =0; j<b.size();j++)
{
cout<<b[j]<<",";
}
cout<<endl;
}
}
void getSub(Set& a, ResSet& res, int i, Set b ,int filter){
if(i==a.size()){
if(b.size()==0){
return;
}
int sum=0;
for(int i = 0; i<b.size();i++){
sum+=b[i];
}
if(sum==filter)
res.push_back(b);
return;
}
getSub(a,res,i+1,b);
b.push_back(a[i]);
getSub(a,res,i+1,b);
}

藤蘿下的陽光

嘿嘿，没有注释，可能比较难懂哦
偷懒没有用数组，用STL的vector<int>代替了（操作方便）

水乡渔夫

#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> Set;//偷懒用STL的vector<int>代替数组了，主要考虑操作方便
typedef vector<vector<int> > ResSet;//结果集

//函数说明 编译工具vc++2003
//用回溯算法（舍弃法）求原集合a的所有满足条件的子集，并存放在结果集res中
//参数说明
//Set& a 原始集合
//ResSet& res 结果集
//int i 用来回溯调用时的退出条件
//int filter=15 用来过滤结果集，也就是子集的元素和应满足的条件
void getSub(Set& a, ResSet& res, int i, Set b,int filter=15);

void main()
{
Set w;//原集合
ResSet res;//子集集合
for(int i = 0; i<10; i++){
w.push_back(i+1);//初始化原集合
}
Set b;//递归调用时用来存放一个子集
getSub(w, res, 0, b);//求结果集
cout<<res.size()<<endl;//满足条件的子集个数
for(unsigned i = 0; i< res.size(); i++)//显示所有满足条件的子集
{
Set b = res[i];
for(unsigned j =0; j<b.size();j++)
{
cout<<b[j]<<",";
}
cout<<endl;
}
}
void getSub(Set& a, ResSet& res, int i, Set b ,int filter){
if(i==a.size()){ //回溯退出条件
if(b.size()==0){
return;
}
int sum=0;
for(int i = 0; i<b.size();i++){
sum+=b[i];
}
if(sum==filter)
res.push_back(b);
return;
}
getSub(a,res,i+1,b);//求舍却了原始集合的第i个元素一个子集
b.push_back(a[i]);
getSub(a,res,i+1,b);//包含了原始集合中的第i个元素的一个子集
}

红苹果

不过我还是看不懂：(
因为我还不会向量呢。