标签：状压DP，位运算
Description
一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥.桥已经很旧了, 所以它不能承受太重的东西.任何时候队伍在桥上的人都不能超过一定的限制. 所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过.队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少.
Input
第一行两个数: w –桥能承受的最大重量(100 <= w <= 400) 和 n –队员总数(1 <= n <= 16). 接下来n行每行两个数分别表示: t – 该队员过桥所需时间(1 <= t <= 50)和 w – 该队员的重量(10 <= w <= 100).
Output
输出一个数表示最少的过桥时间.
Sample Input
100 3
24 60
10 40
18 50
Sample Output
42
题意：N个物品，每个物品有重量Wi和时间Ti，可以选取一些物品组合购买，Wa+Wb+……<=Wmax，对于这些组合购买的物品，只计算其中最大的Ti，使得购买所有物品Ti的总和最小
F[i]表示i状态下最优值，可以先预处理出t[i]和w[i]，之后枚举i之前的状态j，暴力状压，转移枚举子集，使用了一个小技巧加速，否则会TLE
Code
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
inline LL read()
{
LL f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const LL inf=1844387848,ed=1<<18,maxn=20;
LL W,n,a[maxn],b[maxn],f[ed],t[ed],w[ed];
int main()
{
W=read(),n=read();
rep(i,1,n)a[i]=read(),b[i]=read();
rep(i,1,(1<<n)-1)
for(int j=0;(1<<j)<=i;j++)
if(1<<j&i){
w[i]+=b[j+1];
t[i]=max(t[i],a[j+1]);
}//预处理w[i]与t[i]
f[0]=0;
rep(i,1,(1<<n)-1){
if(w[i]<=W)f[i]=t[i];else f[i]=inf;//f[i]初始化
for(int j=(i-1)&i;j;j=(j-1)&i)//注意！！！这里j使用了小技巧加速，可以快速枚举子集
if(w[i^j]<=W)f[i]=min(f[i],f[j]+t[i^j]);
}
printf("%lld\n",f[(1<<n)-1]);
return 0;
}
