题意:

给定一些物品的价值、大小、数量。求一个大小为m的背包最多装得下多少价值的物品。

虽然这道题乱搞都可以AC,但是我们还是实用单调队列优化

这里的f[i]表示容量为i的背包可以装下的最大价值(而不是恰好装下)。因此可以很方便地使用单调队列优化
这所谓的单调队列是神码样的呢?它其实维护了两个单调性:
右边的比左边的新进队。
左边的比右边的优。
为什么这样就对呢?其他单调性为什么不对呢?
这样想:我们至少得维护时间的单调性:也就是右边的比左边的新进队。为什么同时左边的要比右边的优呢?感性地想:在队列中的元素向左侧“流动”时,我们会“失去”非常优秀的解而只能从新进来的解中转移。因此单调性是左边优于右边。
有了单调队列的思路,有了状态转移方程,我们就可以轻松的写出代码。
噢,不知道大家有没有想到这样一个问题:
由于状态转移方程是:
f[i]=max(f[i-kw[i]]+kv[i])
我们不能直接将每个f[i]的值存进队列,而应该保存f[i]-i/w[i]*v[i](仔细想一想为什么)
有了以上这些准备工作,我们的程序差不多就完备了。