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

template
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
void Taking::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
void MaxTaking(Type w[],Type c,int n,bool s[])
{
Taking 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 {
X.r+=w[i];
}
X.Backtrack(0);
if(X.isfind==false)
for(i=0;i {
s[i]=false;
}
}
#include
#include
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 {
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 {
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< outfile.close();
}

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