/**
*Data:2011.3.20
*title:base?on?Branch_board?straight?selection
*/

#include?
#include?
#include?
using?namespace?std;

const?int?D=6;???//總特征數(shù)
const?int?d=2;???//目標(biāo)特征數(shù)
const?int?inf=100000;???//無(wú)窮

int?best[D];????//最好結(jié)果，舍棄對(duì)應(yīng)位置為0
int?max;????????//當(dāng)前最好的結(jié)果的可區(qū)分性
int?q[D-d+1];?????//后繼節(jié)點(diǎn)的個(gè)數(shù)，即下一層舍去的特征數(shù)
int?r[D-d+1];?????//當(dāng)前特征集合的基數(shù)
vector?X;????//當(dāng)前節(jié)點(diǎn)舍棄i個(gè)特征后的剩余特征
vector?Q;????//當(dāng)前節(jié)點(diǎn)后繼舍棄的特征
int?l;????????????//當(dāng)前層數(shù)
int?B;????????????//初始界值
int?J[D+1];???????//判據(jù)值數(shù)組
//任意兩個(gè)特征可區(qū)分性
const?int?cov[6][6]={
		inf13
		3inf5
		67inf
}


class?BTree{
public:
????BTree*?rchild;????//子節(jié)點(diǎn)
????BTree*?lchild;????//左兄弟
????BTree*?parent;????//父節(jié)點(diǎn)
????int????????x;????//舍棄的特征
????void?generateChild（BTree?*）;
};

void?sortByJudge（）;?//根據(jù)判據(jù)值進(jìn)行排序
int??calJudge（vector?&Q?int?x）;?//計(jì)算當(dāng)前節(jié)點(diǎn)判據(jù)值
void?backUp（BTree?*root）;??//回溯
void?updatePath（BTree?*root）;
void?addUnion（vector?&srcint?n）;??//集合相加
void?subUnion（vector?&fir?vector?&sec）;??//集合相減
void?subUnion（vector?&srcint?n）;??????//重載上一個(gè)函數(shù)
void?search（BTree?*root）;???//搜索解
//void?updateUnion（）;?//更新集合
void?freeMem（BTree?*root）;
void?printResult（）;?//輸出結(jié)果

void?BTree::generateChild（BTree?*root）{
????BTree?*node=new?BTree（）;
????root->rchild=node;
????node->parent=root;
????node->x=Q[q[l]-1];

????for（int?i=1;i????????BTree?*node2;
????????//注意最左結(jié)點(diǎn)
????????if（i=q[l]-1）{
????????????node->lchild=NULL;
????????}
????????else{
????????????node2=new?BTree（）;
????????????node->rchild=NULL;
????????????node->lchild=node2;
????????????node2->parent=node;
????????????node2->x=Q[q[l]-i-1];
????????????node=node2;
????????}
????}
????//更新?XQ
????sortByJudge（X）;
????Q.clear（）;
????//May?be?a?bug.
????copy（X.begin（）X.begin（）+q[l]back_inserter（Q））;
????//計(jì)算J表
????for（int?i=0;i????for（int?i=0;i????????J[X[i]=calJudge（XX[i]）;
????}
????subUnion（XQ）;??//更新集合X
}

void?init（）{
????//初始化r和d
????r[0]=D;r[D-d]=0;
????for（int?i=0;i????for（int?i=0;i????????q[i]=r[i]-（D-d-i-1）;
????????r[i+1]=r[i]-q[i];
????}
????B=0;
}

void?search（BTree?*root）{
????l=0;
????while（l>=0）{
????????q[l]=r[l]-（D-d-l-1）;
????????sortByJudge（）;??//排序并更新集合X
????????//判斷下一層是否到達(dá)葉結(jié)點(diǎn)，更新界值
????????if（l+1==D-d）{
????????????if（J[q[l]-1]>B）{
????????????????B=J[q[l]-1];
????????????????updatePath（root->