题目传送门(BZOJ)
>原文链接<

题解 :

状态 :$F[S]$代表状态为$S$下花的最少时间

首先预处理出来每个状态需要花的时间及重量。

对于要更新的状态$i$枚举其子集,若这个$i$对这个子集的补集重量小于限定的重量,就用它来更新$i$。

答案是$F[(1<<n)-1]$

代码 :

#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int N = 16;int W, n, m;int wei[1<<N], tim[1<<N], f[1<<N];int t[N], w[N];int main() { scanf("%d%d", &W, &n); m = 1<<n; for(int i = 0; i < n; i ++ ) scanf("%d%d", &t[i], &w[i]); for(int i = 0; i < m; i ++ ) for(int j = 0; j < n; j ++ ) { if(((1<<j)&i)) wei[i] += w[j], tim[i] = max(tim[i], t[j]); } memset(f, 0x3f, sizeof f); f[0] = 0; for(int i = 1; i < m; i ++ ) { if(wei[i] <= W) f[i] = tim[i]; for(int s = i; s; s = (s-1)&i) { int s1 = i^s; if(wei[s1] <= W) f[i] = min(f[i], f[s]+tim[s1]); } } printf("%d\n", f[m-1]);}