子集树
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn =1e5+5;
int q[maxn];
int x[maxn];
int n,c;
int currV,r;
bool isprinted=false;
void print_ans()
{
for(int i=0;i<=n;++i)
{
if(x[i]) cout<<q[i]<<" ";
}
cout<<endl;
return ;
}
void BackTrack(int t)
{
if(isprinted) return ;
if(currV==c)
{
print_ans();
isprinted=true;
return ;
}
if(t==n)
{
return ;
}
r-=q[t];
if(currV+q[t]<=c)//约束
{
currV+=q[t];
x[t]=1;
BackTrack(t+1);
x[t]=0;
currV-=q[t];
}
if(currV+r>=c)//上界
BackTrack(t+1);
r+=q[t];
}
int main()
{
cin>>n>>c;
long long sum =0;
for(int i =0 ;i<n;++i)
{
cin>>q[i];
sum+=q[i];
}
if(sum<c)
{
cout<<"No Solution!\n";
return 0;
}
r=sum,currV=0;
BackTrack(0);
if(!isprinted)
cout<<"No Solution!\n";
return 0;
}
满m叉树
#include<iostream>
using namespace std;
const int maxn=100+5;
const int inf=1e9;
int c[maxn][maxn],w[maxn][maxn];
int x[maxn][maxn];
int bestx[maxn][maxn];
int n,m,d;
int currC,currW,bestW=inf;
void BackTrack(int t)
{
if(t==n)
{
if(currW<bestW)
{
for(int i =0;i<n;++i) for(int j=0;j<m;++j) bestx[i][j]=x[i][j];
bestW=currW;
}
return ;
}
for(int i =0;i<m;++i)
{
if(currC+c[t][i]<=d && currW+w[t][i]<bestW)
{
currC+=c[t][i],currW+=w[t][i];
x[t][i]=1;
BackTrack(t+1);
currC-=c[t][i],currW-=w[t][i];
x[t][i]=0;
}
}
}
int main()
{
cin>>n>>m>>d;
for(int i =0 ;i<n;++i)
for(int j=0;j<m;++j)
cin>>c[i][j];
for(int i =0 ;i<n;++i)
for(int j=0;j<m;++j)
cin>>w[i][j];
BackTrack(0);
if(bestW!=inf)
{
cout<<bestW<<endl;
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
if(bestx[i][j]) cout<<j+1<<" ";
}
}
cout<<endl;
}
}
排列树
待续