Question

计算机算法设计之子集和数问题

[参考数据类型或变量]
float s; // 表示有可能抵达答案节点的子路径上的元素之和；
float r; // 尚未测试的剩余集合元素之和；
float w[n]; // 存储原始集合的n个元素, 根据问题实例初始化；
[参考子程序接口与功能描述]
void RecursiveSubset(float s, float r, int k)
功能: 针对问题实例的递归回溯算法。
void IterativeSubset(float s, float r, int k)
功能: 针对问题实例的迭代回溯算法。
void InitializeInstanse(void)�0�0 功能: 问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r。

麻烦大家给出可以编译连接的程序源代码，我需要上机检测，谢谢~~~

Answer 1

template<class Type>
class Taking{
friend void MaxTaking(Type w[],Type c,int n,bool s[]);
private:
void Backtrack(int);
int n;
Type* w,c,cw,r;
bool* s;
bool isfind;
};
template<class Type>
void Taking<Type>::Backtrack(int i)
{
if(!isfind)
{
if(i>=n)
{
if(cw==c)
isfind=true;
return;
}
r-=w[i];
if(cw+w[i]<=c)
{
s[i]=true;
cw+=w[i];
Backtrack(i+1);
cw-=w[i];
}
if((cw+r>=c)&&(!isfind))
{
s[i]=false;
Backtrack(i+1);
}
r+=w[i];
}
}
template<class Type>
void MaxTaking(Type w[],Type c,int n,bool s[])
{
Taking<Type> X;
X.w=w;
X.c=c;
X.n=n;
X.cw=0;
X.r=0;
X.s=s;
X.isfind=false;
for(int i=0;i<n;i++)
{
X.r+=w[i];
}
X.Backtrack(0);
if(X.isfind==false)
for(i=0;i<n;i++)
{
s[i]=false;
}
}
#include<iostream.h>
#include<fstream.h>
void main()
{
fstream outfile;
outfile.open("input.txt",ios::in);
char ch;
int n=0;
int *a,c=0;
bool *s;
do
{
outfile.get(ch);
} while(ch>'9'||ch<'0');
while(ch<'9'&&ch>'0')
{
n*=10;
n+=ch-'0';
outfile.get(ch);
}
a=new int[n];
s=new bool[n];
outfile.get(ch);
while(ch<'9'&&ch>'0')
{
c*=10;
c+=(int)(ch-'0');
outfile.get(ch);
}

for(int i=0;i<n;i++)
{
a[i]=0;
do
{
outfile.get(ch);
} while(ch>'9'||ch<'0');
while(ch<'9'&&ch>'0')
{
a[i]*=10;
a[i]+=(int)(ch-'0');
outfile.get(ch);
}
}
outfile.close();
MaxTaking(a,c,n,s);
outfile.open("output.txt",ios::out);
char* m=new char[200];
int mpoint=0;
for(i=0;i<n;i++)
{
if(s[i]==true)
{
int w=a[i];
while(w!=0)
{
m[mpoint++]=w%10+'0';
w=w/10;
}
m[mpoint++]=' ';
}
}
m[mpoint]='\0';
if(mpoint==0)
outfile<<"NO SOLUTION!\n";
else
outfile<<m<<"\n";
outfile.close();
}

Answer 2

input.txt内容
3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2