一.01背包dfs

//回溯法，01背包
#include
#include
using namespace std;
const int N=10;
int n,C;
int v[N],W[N];
double bestp;//当前最优值
double cw;
double cp;
int bestx[N];
int x[N];
typedef struct obj{
int w;
int v;
};
obj objt[N];
bool cmp(const obj a,const obj b)
{
return a.v/a.w>b.v/b.w;
}
int upbound(int i)//求i到后面n能装入的最大值
{
double cleft=C-cw;
double brp=0.0;
while(i<=n&&objt[i].wn)//到达叶子节点 ，也就说明已经存在了一条路径
{
for(int j=1;j<=n;j++) { bestx[j]=x[j]; } bestp=cp;//保存当前最大价值 return ; } if(cw+objt[t].w<=C)//如果满足条件，装入，走左分支 { x[t]=1; cw+=objt[t].w; cp+=objt[t].v; dfs(t+1);//往下扩展 cw-=objt[t].w;//回溯 cp-=objt[t].v; } if(upbound(t+1)>bestp)//不满足条件则判断是否可能构成最优解
{
x[t]=0;
dfs(t+1);//往下扩展
}
}
int main()
{
cin>>n>>C;
for(int i=1;i<=n;i++) { cin>>objt[i].w>>objt[i].v;
}
sort(objt+1,objt+n+1,cmp);
dfs(1);
cout<<bestp<<endl;
cout<<"装入的价值分别是"<<endl;
for(int i=1;i<=n;i++)
{
if(bestx[i]==1)
{
cout<<objt[i].v<<' ';
}
}
return 0;
}

二.最大团问题

若一个图的每一对不同顶点恰有一条边相连，则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n − 1) / 2条边，以Kn表示。它是(k − 1)-正则图。所有完全图都是它本身的团(clique)。