题目链接：http://hihocoder.com/problemset/problem/1137
题意：有N个员工来面试，已知每个人的价值和薪水，公式收人的要求是：1.要x男y女，2.这x+y个员工的总薪水不能超过B，3.在前两点的前提上要是要使总价值最大，基于此还要使总薪水最小。4.如果答案不唯一，选择员工编号的字典序最小的方案。
要求输出选择员工的总价值和总薪水，并且输出他们的编号。
解析：本来看到总共就100的数据，就去深搜，结果超时很多，看到题解是背包的题目，感觉是很好的题目，希望以后遇到这种题能A出来，下面题解讲的很好，题解：hiho一下第83周《Recruitment》题目分析
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define M 105
int n,x,y,b;
struct node{int v,s,id;
}mlist[M],flist[M];
int totv,tots,mp[1005],fp[1005];//p[v]表示总薪水不超过v时，获得最大价值的总薪水值。
int maleNum,femaleNum;
int mf[M][M][1005]; //表示前i个男员工中选择j个，总薪水恰好为k的价值。若不存在合法方案，价值为0。
int ff[M][M][1005]; //表示前i个女员工中选择j个，总薪水恰好为k的价值。若不存在合法方案，价值为0。
int mg[M][M][1005]; //若mf[i][j][k]存在合法方案，则g[i][j][k]表示该方案中最后选取的员工序号，否则为-1。
int fg[M][M][1005]; //若ff[i][j][k]存在合法方案，则g[i][j][k]表示该方案中最后选取的员工序号，否则为-1。
vector<int>ans;
int main()
{int i,j,k;char op;scanf("%d%d%d%d",&n,&x,&y,&b);maleNum=femaleNum=0;getchar();for(i=1;i<=n;i++){scanf("%c%d%d",&op,&j,&k);if(op=='M'){maleNum++;mlist[maleNum].id=i;mlist[maleNum].v=j;mlist[maleNum].s=k;}else{femaleNum++;flist[femaleNum].id=i;flist[femaleNum].v=j;flist[femaleNum].s=k;}getchar();}//先处理男方memset(mf,0,sizeof(mf));memset(mg,-1,sizeof(mg));mg[0][0][0]=0;//dp求mf数组for(i=1;i<=maleNum;i++){for(j=0;j<=x;j++){for(k=0;k<=b;k++){mf[i][j][k]=mf[i-1][j][k];mg[i][j][k]=mg[i-1][j][k];if(j>0&&k>=mlist[i].s&&mg[i-1][j-1][k-mlist[i].s]!=-1&&mf[i][j][k]<mf[i-1][j-1][k-mlist[i].s]+mlist[i].v){mf[i][j][k]=mf[i-1][j-1][k-mlist[i].s]+mlist[i].v;mg[i][j][k]=i;}}}}//将B的总薪水分配给男女两边时//计算男方总薪水不超过i时，获得最大价值的总薪水值。memset(mp,-1,sizeof(mp));for(i=0;i<=b;i++){if(i>0)mp[i]=mp[i-1];if(mg[maleNum][x][i]!=-1){if(mp[i]==-1){mp[i]=i;}else{if(mf[maleNum][x][i]>mf[maleNum][x][mp[i]]){mp[i]=i;}}}}//处理女方memset(ff,0,sizeof(ff));memset(fg,-1,sizeof(fg));fg[0][0][0]=0;//dp求ff数组for(i=1;i<=femaleNum;i++){for(j=0;j<=y;j++){for(k=0;k<=b;k++){ff[i][j][k]=ff[i-1][j][k];fg[i][j][k]=fg[i-1][j][k];if(j>0&&k>=flist[i].s&&fg[i-1][j-1][k-flist[i].s]!=-1&&ff[i][j][k]<ff[i-1][j-1][k-flist[i].s]+flist[i].v){ff[i][j][k]=ff[i-1][j-1][k-flist[i].s]+flist[i].v;fg[i][j][k]=i;}}}}//将B的总薪水分配给男女两边时//计算女方总薪水不超过i时，获得最大价值的总薪水值。memset(fp,-1,sizeof(fp));for(i=0;i<=b;i++){if(i>0)fp[i]=fp[i-1];if(fg[femaleNum][y][i]!=-1){if(fp[i]==-1){fp[i]=i;}else{if(ff[femaleNum][y][i]>ff[femaleNum][y][fp[i]]){fp[i]=i;}}}}//计算怎么将总薪水b分配给男女两边tots=totv=0;for(i=0;i<=b;i++){if(mp[i]!=-1&&fp[b-i]!=-1&&totv<mf[maleNum][x][mp[i]]+ff[femaleNum][y][fp[b-i]]){totv=mf[maleNum][x][mp[i]]+ff[femaleNum][y][fp[b-i]];//totv即是最大总价值tots=i; //mp[tots]是给男方的总薪水}}//利用g数组,当给定一方总薪水时，可以求解出对应总薪水的合法方案。//男方选中人员i=maleNum; j=x; k=mp[tots];while(j>0){i=mg[i][j][k];ans.push_back(mlist[i].id);j=j-1;k=k-mlist[i].s;i=i-1;}//女方选中人员i=femaleNum; j=y; k=fp[b-tots];while(j>0){i=fg[i][j][k];ans.push_back(flist[i].id);j=j-1;k=k-flist[i].s;i=i-1;}printf("%d %d\n",totv,mp[tots]+fp[b-tots]);sort(ans.begin(),ans.end());vector<int>::iterator it;for(it=ans.begin();it!=ans.end();it++){printf("%d ",*it);}printf("\n");return 0;
}超时深搜：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
#define M 105
int n,x,y,b;
struct node{char g;int v,s;
}a[M];
int totV,totS;
bool vis[M],temp[M];
void dfs(int it,int m,int f,int tv,int ts)// 该考虑it号应聘者，已经选了m男，f女，总能力值为tv，总工资为s
{if(ts>b||m>x||f>y)return;if(m==x&&f==y){if(tv>totV){totV=tv;totS=ts;for(int i=1;i<=n;i++)vis[i]=temp[i];}return;}for(int i=it;i<=n;i++){if(a[i].s>b)continue;if(a[i].g=='M'){if(m<x){temp[i]=true;dfs(i+1,m+1,f,tv+a[i].v,ts+a[i].s);temp[i]=false;dfs(i+1,m,f,tv,ts);}}else{if(f<y){temp[i]=true;dfs(i+1,m,f+1,tv+a[i].v,ts+a[i].s);temp[i]=false;dfs(i+1,m,f,tv,ts);}}}
}
int main()
{int i,j;scanf("%d%d%d%d",&n,&x,&y,&b);getchar();for(i=1;i<=n;i++){scanf("%c%d%d",&a[i].g,&a[i].v,&a[i].s);getchar();}totV=totS=0;memset(vis,false,sizeof(vis));memset(temp,false,sizeof(temp));dfs(1,0,0,0,0);printf("%d %d\n",totV,totS);for(j=1;j<=n;j++){if(vis[j])printf("%d ",j);}printf("\n");return 0;
}