2333，暴力，枚举集合再枚举子集。。（一开始判时间直接sb到每一次都重算，，呵呵呵，真是虚傻弱，，）
1 #include <bits/stdc++.h> 2 #define LL long long 3 #define inf 0x3f3f3f3f 4 using namespace std; 5 inline int ra() 6 { 7 int x=0,f=1; char ch=getchar(); 8 while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} 9 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} 10 return x*f; 11 } 12 int W,n; 13 int f[1<<17],w[20],t[20],sum[1<<17]; 14 int main(int argc, char const *argv[]) 15 { 16 W=ra(); n=ra(); 17 for (int i=1; i<=n; i++) 18 t[i]=ra(),w[i]=ra(); 19 for (int i=0; i<=(1<<n); i++) f[i]=inf; 20 for (int i=0; i<n; i++) 21 f[(1<<i)]=t[i+1],sum[(1<<i)]=w[i+1]; 22 for (int i=1; i<(1<<n); i++) 23 { 24 for (int j=i&(i-1); j; j=i&(j-1)) 25 { 26 if (sum[j]+sum[i-j]<=W) f[i]=min(f[i],max(f[j],f[i-j])); 27 else f[i]=min(f[i],f[i-j]+f[j]); 28 sum[i]=sum[j]+sum[i-j]; 29 } 30 } 31 cout<<f[(1<<n)-1]; 32 return 0; 33 }