n≤16，想到状压DP。
注意枚举子集的方法：for(int j=i;j;j=i&(j-1))。
#SXOI2016之蜜汁错误# 感觉自己简直蠢哭，考场上连个状压都想不出来。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 70000
using namespace std;
int m,n;
int t[maxn],w[maxn],mx[maxn],sum[maxn],f[maxn];
inline int read()
{
int x=0,f=1;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;
}
int main()
{
memset(f,127,sizeof(f));
f[0]=0;
m=read();n=read();
F(i,1,n) t[i]=read(),w[i]=read();
F(i,1,(1<<n)-1) F(j,1,n) if (i&(1<<(j-1))) mx[i]=max(mx[i],t[j]),sum[i]+=w[j];
f[0]=0;
F(i,1,(1<<n)-1) for(int j=i;j;j=i&(j-1)) if (sum[j]<=m) f[i]=min(f[i],mx[j]+f[i^j]);
printf("%d\n",f[(1<<n)-1]);
return 0;
}
原文：http://blog.csdn.net/aarongzk/article/details/51195447