一样，从\(n\le 16\)启发用状压dp

思路

本质上与UVA11825 Hackers' Crackdown异曲同工，不过可以通过预处理处理出一组人的集合
时间复杂度最坏为\(O(2^{2n})\)，当任何一个集合中体重之和都\(\le W\)，但实际运行起来很快

代码

#include <bits/stdc++.h>

using namespace std;
const int N=17,INF=0x3f3f3f3f;

int W,n,bound;
int t[N],w[N];

int S[1<<N],T[1<<N],cnt;
int f[1<<N];

void init() {
	bound=(1<<n)-1;
	for(int i=1;i<=bound;i++) {
		int sum=0,allt=0;
		for(int j=0;j<n;j++)
			if(i>>j&1) {
		  		sum+=w[j];
				allt=max(allt,t[j]);
			}
		if(sum<=W) {
		  	S[++cnt]=i;
			T[cnt]=allt;
		}
	}
}

int main() {
	scanf("%d%d",&W,&n);
	for(int i=0;i<n;i++)
	  scanf("%d%d",&t[i],&w[i]);
	init();	//预处理
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=0;i<=bound;i++) {
		if(f[i]==INF) continue;
		for(int j=1;j<=cnt;j++) {
			int k=S[j];
			if((i&k)!=0) continue;	//无交集
			f[i|k]=min(f[i|k],f[i]+T[j]);	//状态转移
		}
	}
	printf("%d",f[bound]);
	return 0;
}