好久 好久 好久 没搞过多重背包的题了，不过还是挺模版的。加上二进制优化了，不加目测会超时。

每次都感觉自己写的转换二进制，这么搓呢。。。

1 #include 
     
       2 #include 
      
        3 #define N 100001 4 int p[N],v[N]; 5 int main() 6 { 7     int i,j,k,c,num,n,sum,vv,max; 8     while(scanf("%d",&c)!=EOF) 9     {10         memset(p,0,sizeof(p));11         memset(v,0,sizeof(v));12         scanf("%d",&n);13         j = 1;14         for(i = 1;i <= n;i ++)15         {16             scanf("%d%d",&num,&vv);17             sum = vv*num;k = vv;18             for(;;)19             {20                 if(sum <= 0)21                 break;22                 sum -= k;23                 v[j] = k;24                 j ++;25                 k *= 2;26                 if(k > sum)27                 {28                     if(sum != 0)29                     {30                         v[j] = sum;31                         j ++;32                     }33                     break;34                 }35             }36         }37         n = j-1;38         for(i = 1;i <= n;i ++)39         {40             for(j = c;j >= v[i];j --)41             {42                 if(p[j] < p[j-v[i]]+v[i])43                 p[j] = p[j-v[i]]+v[i];44             }45         }46         max = 0;47         for(i = 1;i <= c;i ++)48         if(max < p[i])49         max = p[i];50         printf("%d\n",max);51     }52     return 0;53 }