package 线性dp.背包模型;

/**
 * 与完全背包不同的是每个物品最多选s[i]个
 * 状态定义:f[i,j]前i个物品可选,体积最大为j的最大价值
 * 状态划分:选第i组物品的第1个,选第i组物品的第2个,选第i组物品的第s[i]个,和不选第i组物品
 * 状态计算:显然不选第i组物品就是f[i-1,j]
 * |________|+w[i][1]
 * |________|+w[i][2]
 * ....
 * |________|+w[i][k]
 * 前面的最大值如何计算
 * 前面的可以取的范围i-1组的物品,要选第i组的第k个物品,就要腾出来这么多
 * 那么结合状态定义,最大价值就是:f[i-1,j-v[i][k]]+w[i][k]
 * 选第i组物品的计算:选第i组物品的第k个,显然就是f[i-1,j-v[i][k]]+w[i][k]
 */
public class 多重背包单调队列优化 {
    public static void main(String[] args) {

    }
}