多重背包问题

---

多重背包问题(限制其物品的个数，介于无限和唯一之间)

一种方法是压入k个物品i，转变成01背包问题，但是还可以简化一下，f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}，这样一来就可以简化为完全背包问题的方法，path[][]长度得到压缩。

        for(j=weight[i];j<=volumn;j++){   // 需要重叠，所以从左到右
            for(k=1;k<=j/weight[i];k++){
                 if(dp[j-k*weight[i]]+k*value[i]>dp[j]){
                       path[i][j]=1;
                       dp[j]=dp[j-k*weight[i]]+k*value[i];
                     }
            }
        }