动态规划背包问题-多重背包

多重背包问题	背包问题系列
问题描述	给定N个物品，其中第i种物品的体积为$V_i$，价值为$W_i$，并且有$C_i$个。有一个容积为M的背包，要求选择一些物品放入背包，使得物品总体积不超过M的前提下，物品总价值和最大。
问题转换	将第i种物品看作独立的$C_i$个物品，从而转换为共有$\sum\limits_{i=1}^{N}C_i$个物品的0/1背包问题
问题转换	将数量为$C_i$的第i个物品拆成p+2个物品，他们的体积分别为：$2^0V_i,2^1V_i,\dots,2^pV_i,R_iV_i$，其中$R_i=C_i-2^0-2^1-\dots-2^p$
问题优化	可借助单调队列优化