又是几天不做题，一个二进制优化的多重背包让我写的狗屁不通，错漏百出！TLE， WA了好几次，都是细节啊。

思路，很裸的多重背包。

My Code:

 

1 #include 
     
        2 #include 
      
         3 #include 
       
          4  5 using namespace std;  6  7 const int N = 100010;  8 const int M = 1024;  9 10 int f[N]; 11 int k[M], c[M]; 12 13 int Max(int x, int y) {
   14     return x > y ? x : y; 15 } 16 17 18 int main() {
   19     //freopen("data.in", "r", stdin); 20 21     int V, n, m, i, j; 22     while(~scanf("%d%d", &V, &n)) {
   23         for(i = 0; i < n; ++i) {
   24             scanf("%d%d", k + i, c + i); 25         } 26 27         for(i = 0; i <= V; ++i)    f[i] = 0; 28 29         for(i = 0; i < n; ++i) {
   30             if(k[i]*c[i] > V) {    //complete pack 31                 for(j = c[i]; j <= V; ++j) {
   32                     f[j] = Max(f[j], f[j - c[i]] + c[i]); 33                 } 34             } else {    //zero one pack with binary optimize 35                 m = 1; 36                 while(k[i]) {
   37                     if(m > k[i])    m = k[i]; 38                     k[i] -= m; 39                     for(j = V; j >= c[i] * m; --j) {
   40                         f[j] = Max(f[j], f[j - c[i] * m] + c[i] * m); 41                     } 42                     m <<= 1; 43                 } 44             } 45         } 46         printf("%d\n", f[V]); 47     } 48     return 0; 49 }