【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2073
【题目大意】
任何时候队伍在桥上的人都不能超过一定的限制.
所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过.
队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,
每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少.
【题解】
我们首先预处理出每种组合的总重量和过桥需要的时间，
之后顺序枚举集合，枚举其子集，如果符合拆分要求则进行转移即可。
【代码】
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=65536;
int W,n,t[20],w[20],dp[N],s[N],d[N];
int main(){
memset(dp,INF,sizeof(dp));
scanf("%d%d",&W,&n);
int all=1<<n;
for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&w[i]);
for(int i=1;i<all;i++){
for(int j=1;j<=n;j++){
if(i&(1<<(j-1))){d[i]=max(d[i],t[j]);s[i]+=w[j];}
}
}dp[0]=0;
for(int i=1;i<all;i++){
for(int j=i;j;j=i&(j-1))if(s[j]<=W)dp[i]=min(dp[i],d[j]+dp[i^j]);
}printf("%d\n",dp[all-1]);
return 0;
}