很简单的子集枚举状压dp
这个 (j-1)&i
的子集枚举是真的骚气
#include <bits/stdc++.h>
using namespace std;
int W,n,t[20],w[20],st[99999],sw[99999],f[99999];
int main() {
cin>>W>>n;
for(int i=1;i<=n;i++) cin>>t[i]>>w[i];
for(int i=0;i<1<<n;i++) {
for(int j=1;j<=n;j++) {
if(i&(1<<(j-1))) st[i]=max(st[i],t[j]),sw[i]+=w[j];
}
}
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<1<<n;i++) {
for(int j=i;j;j=(j-1)&i) {
if(sw[j]<=W) f[i]=min(f[i],f[i^j]+st[j]);
}
}
cout<<f[(1<<n)-1]<<endl;
}