Knapsack - MultiplePack - O(VN) 多重背包中多次背包 O(VN) 算法

http://massivealgorithms.blogspot.com/2015/06/knapsack-multiplepack.html
多重背包中多次背包 O(VN) 算法2 (线性动规) 带参考程序_sy2006
其实解决多次背包问题还可以用线性动规的方法（类似NOIP2009普及组道路游戏的算法）
设背包容量t，物品件数n，每件物品体积m[i]，价值s[i]，可用次数c[i](0表示无限制)
用 b[j,i] 记录到容量为j的情况下物品i使用次数，f[j] 记录容量为j的情况的最优解。
动规的时候，将j从1到t循环一次，分别求解f[j]
对于每个f[j],可以从f[j-m[i]] (i=1..n)得来
转移方程为f[j]=max(f[j-m[i]]+s[i]) (i=1..n, 且满足 j>=m[i] , b[j-m[i],i]<c[i])
            且 b[j]=b[j-m[i]]; b[j,i]:=b[j,i]+1;

多重背包问题 转化为 完全背包问题，也就是每个物品都有无限个，但是在循环过程中用一个数组记录 ：某种硬币i使用的次数，如果使用次数超过c［i]，则停止循环. 时间复杂度就是O(n*m)
poj 1742 Coins(多重背包)
http://www.cnblogs.com/E-star/archive/2011/12/08/2280973.html

给定n种面值的硬币面值分别为wi个数为ci，问用这些硬币可以组成1~m之间的多少面值
解题思路：楼教主的男人八题之一，算是一个经典的问题，定义一个sum数组。每次填dp[j]时直接由dp[j-weight[i]]推出，
          前提是sum[j-w[i]]<c[i].sum每填一行都要清零，sum[j]表示当前物品填充j大小的包需要至少使用多少个.复杂度O(n*m)

    while(scanf("%d%d",&n,&V),n+V)
    {
        int ans=0;
        for(i=0;i<n;i++)
        scanf("%d",&w[i]);
        for(i=0;i<n;i++)
        scanf("%d",&b[i]);
        for(i=f[0]=1;i<=V;i++) f[i]=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<=V;j++) sum[j]=0;//关键是用sum来限定了次数
            for(j=w[i];j<=V;j++)//从w[i]到V循环检查看是否能够出现前边没有出现的价格
            {
                if(!f[j]&&f[j-w[i]]&&sum[j-w[i]]<b[i])
                //如果j价格没有出现过，且j-w[i]出现过，并且使用i硬币的次数没有超出给定的数量
                {
                    f[j]=1;//标记为已出现过
                    sum[j]=sum[j-w[i]]+1;//使用次数+1
                    ans++;//满足条件++
                }
            }
        }
        cout<<ans<<endl;
    }

Read full article from 多重背包中多次背包 O(VN) 算法2 (线性动规) 带参考程序_sy2006