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);
  }
}

• Re:贴个“多重背包”O(N*V)算法（使用单调队列） (3247) zhouzixuan 2013-10-20 20:32:14