题目描述

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出结果：10

单调队列优化 $O(n^2)$

算法详细解释

设背包的总体积为m
先将f[]数组初始化为只考虑前i-1个物品的情况下的最优解
在只考虑前i的物品的情况下：
    设第i类物品的体积为v,数量为s，价值为w
    f[j]表示考虑前i个物品时，背包体积为j时的最优解，j的取值范围为[0,m]
    对于任意的j，都存在递推式 f[j]=max({f[j-kv]+kw | k>=0 && k<= min(s,floor(m/v) ) }); 
    其中floor表示向下取整。
    则可知
        f[m]=max({f[m-kv]+kw | k>=0 && k<= min(s,floor(m/v) ) });
        设y=m-kv 则y是关于k的因变量
            k的取值范围：k>=0 && k<= floor(m/v) 注意这里和上面k的取值范围的区别,这里
            可没有考虑物品的数量
            y的取值范围：[0,v-1]可以看出y的取值范围和第i个物品的体积v有关

        由y=m-kv可知 m=y+kv 则
        f[y+kv]=max({f[y]+xw | x>=0 && x<=k ) });

        令y不变，k变
        则有：
        f[y]= max({ f[y] });
        f[y+v] =max({ f[y], f[y]+w })
        ...
        f[y+kv] = max({f[y]+xw | x>=0 && x<=k ) });

        观察上面可知，每次都往max({})中添加一个元素f[y+(k-1)v]+(k-1)w 
        每次添加都要获取最大值，因此可以使用单调队列来快速获取最大值
        (这里是不是可以用其他结构获取最大值？)

        单调队列时间复杂度是线性的，由于kv+y=m 且 y的取值范围必须小于v，因此k=(m-y)/v<(m-v)/v=m/v-1
        所以在y不变的情况下，只需要循环不超过m/v-1次，又 y<v 因此 y*(m/v-1) < m-v 
        所以对于考虑前i个物品时，获取到f[m]的值的时间复杂度为 O(m) 

        对于考虑前n个物品时，的时间复杂度为 O(nm) 即平方级别