> 
> http://www.cppblog.com/flyinghearts/archive/2010/09/01/125555.html
> 文章比较长，这里只做个简短的说明。
> 
> “多重背包”的ＤＰ状态方程：
> F[i][j] = max { F[i - 1] [j – k * v[i] ] + k * w[i] }  (0 <= k <= m[i]) 
> 
> 算法：
> 　　先对要求最值的几项进行调整（要减去某个变值，才能保证几次求最值的几项出现重复），再放入一个队列，最后实现在O(1)时间内求这个队列的最大值（用一个辅助队列——单调队列，记录该队列的最大值）。
> 
> 
> 
> “多重背包”通用模板函数：
> 
> const int MAX_V = 100004;
> //v、n、w：当前所处理的这类物品的体积、个数、价值
> //V：背包体积， MAX_V：背包的体积上限值
> //f[i]：体积为i的背包装前几种物品，能达到的价值上限。
> inline void pack(int f[], int V, int v, int n, int w)
> {
>   if (n == 0 || v == 0) return;
>   if (n == 1) {               //01背包
>     for (int i = V; i >= v; --i)
>       if (f[i] < f[i - v] + w) f[i] = f[i - v] + w;
>     return;
>   }
>   if (n * v >= V - v + 1) {   //完全背包(n >= V / v)
>     for (int i = v; i <= V; ++i)
>       if (f[i] < f[i - v] + w) f[i] = f[i - v] + w;
>     return;    
>   }
> 
>   int va[MAX_V], vb[MAX_V];   //va/vb: 主/辅助队列
>   for (int j = 0; j < v; ++j) {     //多重背包
>     int *pb = va, *pe = va - 1;     //pb/pe分别指向队列首/末元素
>     int *qb = vb, *qe = vb - 1;     //qb/qe分别指向辅助队列首/末元素  
>     for (int k = j, i = 0; k <= V; k += v, ++i) {
>       if (pe  == pb + n) {       //若队列大小达到指定值，第一个元素X出队。
>         if (*pb == *qb) ++qb;   //若辅助队列第一个元素等于X，该元素也出队。 
>         ++pb;
>       }
>       int tt = f[k] - i * w;
>       *++pe = tt;                  //元素X进队
>       //删除辅助队列所有小于X的元素，qb到qe单调递减，也可以用二分法
>       while (qe >= qb && *qe < tt) --qe;
>       *++qe = tt;              //元素X也存放入辅助队列        
>       f[k] = *qb + i * w;      //辅助队列首元素恒为指定队列所有元素的最大值
>     }
>   }
> }
> 
> 针对v和w相等的情况，可以用f[i]表示容量为i的背包，是否恰好装满前面的某些物品。
> 下面的代码耗时1875ms，可以进行如下优化：排序、数组va和f进行交换、避免对队列长度的判断。
> 大概能优化到1s左右，比直接用“状态　+ 计数”的方法要慢。
> 
> 
> 代码：
> 
> #include<cstdio>
> 
> //MAX_N 物品种类数最大值 MAX_n每种物品数目的最大值，MAX_V背包体积最大值
> const int MAX_N = 101, MAX_V = 100004;
> 
> //w = v特例
> inline void pack(bool f[], int V, int v, int n, int& total)
> {
>   //if (n == 0 || v == 0) return;
>   if (n == 1) {  //01背包
>     for (int i = V; i - v >= 0; --i)
>       if (! f[i] && f[i - v]) f[i] = true, ++total;
>     return;
>   }
>   if (n * v >= V - v + 1) {  //完全背包 n >= V / v
>     for (int i = v; i <= V; ++i)
>       if (! f[i] && f[i - v]) f[i] = true, ++total;
>     return;
>   }
> 
>   bool va[MAX_V];
>   for (int j = 0; j < v; ++j) {     //多重背包
>     bool *pb = va, *pe = va - 1; 
>     size_t sum = 0;
>     for (int k = j; k <= V; k += v) {
>       if (pe == pb + n) sum -= *pb++;  //队列已满，队首元素出队
>       *++pe = f[k];  //进队
>       sum += f[k];     
>       if (! f[k] && sum != 0) f[k] = true, ++total; 
>       //f[k] = (bool)sum;       
>     }
>   }  
> }
> 
> int main()
> {
>   //freopen("src.txt","r",stdin);
>   //freopen("z-e.txt","w",stdout);
>   int v[MAX_N], n[MAX_N];
>   int V, N;
>   bool f[MAX_V];
>   while (scanf("%d %d",&N,&V) != EOF) {
>     if (N + V == 0) break;
>     for (int i = 0; i < N; ++i) scanf("%d", &v[i]);
>     for (int i = 0; i < N; ++i) scanf("%d", &n[i]);
>     int total = 0;
>     f[0] = true;
>     for (int i = 1; i <= V; ++i) f[i] = false;
>     for (int i = 0; i < N; ++i) pack(f,V,v[i],n[i], total);
>     printf("%d\n",total);
>   }
> }

ORZ!!