poj 1276 多重背包

题目链接：http://poj.org/problem?id=1276

题目就是 重量=价值 的多重背包

详细解法参照大牛们编写的《背包九讲》

状态转移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

要注意在输入数据中cash N n1 D1 n2 D2 ... nN DN 

cash小于所有D1...DN的情况，这种情况输出0

我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int max(int a,int b)
{
    if(a>b)
        return a;
    else return b;
}
int main(int argc, char** argv) {
    int i,i1,i2,n,m,a[2][1005],f[100005],flag;
    
    while(scanf("%d",&m)!=EOF)
    {
        flag=1;
        memset(f,0,sizeof(f));
        scanf("%d",&n);
      
        
        for(i=0;i<n;++i)
        {
            scanf("%d %d",&a[0][i],&a[1][i]);
            if(a[1][i]<=m)
                flag=0;
        }
       if(n==0||m==0||flag==1)
            printf("0\n");
       else
       {
       for(i=0;i<n;++i)
       {
           for(i1=1;a[0][i]>=i1;i1=i1*2)
           {
               for(i2=m;i2>=1;i2--)
               {
                   if(i1*a[1][i]<=i2)
                   f[i2]=max(f[i2],f[i2-i1*a[1][i]]+i1*a[1][i]);
               }
               a[0][i]-=i1;
           }
           if(a[0][i]!=0)
           {
               for(i2=m;i2>=1;i2--)
               {
                   if(a[0][i]*a[1][i]<=i2)
                   f[i2]=max(f[i2],f[i2-a[0][i]*a[1][i]]+a[0][i]*a[1][i]);
               }
           }
       }
        
        printf("%d\n",f[m]);
        }
    }
    return (EXIT_SUCCESS);
}