poj 1742 多重背包（单调队列）

本文主要是介绍poj 1742 多重背包（单调队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如题:http://poj.org/problem?id=1742

,...又是这道题，第一种方法是二进制拆分多重背包（能过hdu2488 见我这一篇http://blog.csdn.net/twenty_seven/article/details/43152441），

第二种是为了减小时间复杂度，通过改变dp策略（能过poj1742 不能过杭电）http://blog.csdn.net/twenty_seven/article/details/43159861，

这里说第三种，多重背包的0（VN）复杂度算法。使用了单调队列。

这位大牛写的很清楚http://blog.csdn.net/flyinghearts/article/details/5898183。

也就是找出状态转移方程中的重复状态，然后将容量拆成v拆成余数和整数部分。通过等间距的几步的最大值推出下一个状态。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int w[103];
int num[103];
int f[100005],q[100005];
int n,m;
int main()
{
// freopen("C:\\1.txt","r",stdin);
while(~scanf("%d%d",&n,&m)&&n&&m)
{
  int i,j,d;
  memset(f,0,sizeof(f));
  for(i=1;i<=n;i++)
   scanf("%d",&w[i]);
  for(i=1;i<=n;i++)
   scanf("%d",&num[i]);
  f[0]=1;
  int ret=0;
  for(i=1;i<=n;i++)
  {
   if(num[i]==1){
    for(j=m;j>=w[i];j--){
     if(!f[j]&&f[j-w[i]])
     {
      f[j]=1;
      ret++;
     }
    }
   }
   else if(num[i]*w[i]>=m)
   {
    for(j=w[i];j<=m;j++)
     if(!f[j]&&f[j-w[i]])
     {
      f[j]=1;
      ret++;
     }
   }
   else
   {
    for(d=0;d<w[i];d++)
    {
     int st=0,ed=-1,sum=0;
     for(j=d;j<=m;j+=w[i])
     {
      if(st+num[i]==ed)
       sum-=q[st++];
      q[++ed]=f[j];
      sum+=f[j];
      if(!f[j]&&sum)
      {
       f[j]=1;
       ret++;
      }
     }
    }
   }
  }
  printf("%d\n",ret);
}
}