T1.Coins(POJ1742)

多重背包最基本的状态转移方程是这样的: 用f[i][j]表示前i个物品装进背包占容量为j时的最大价值。
$$

题意:

求用n种硬币每种c[i]个最多可以凑出多少种面额?

二进制优化:

作为将$O(NV\sum{\frac{V}{w[i]}})$也就是$O(N^2V)$级别的算法优化成$O(V\sum{log(c[i])})$的方法,自然少不了对"2"灵活的应用。
由于这种方案的优化效果不是非常好,无法顺利通过本题,而且大家肯定已经可以熟练运用,这里暂不讨论。


单调队列优化:

$O(K\times logN)$的算法再经过某些基于单调性的脑洞级优化后,会变成惊人的$O(K\times 1)$而这道题用到的当然就是这种方法。
观察f[i][j]是由哪些东西的最小值转移过来的:

所以,对于这道题,我们要知道的就是红色格子里有没有可以达到的容量。而红色格子是连续的最多c[i]个。
这不是so-easy的东西吗?

下面具体介绍几种解决方法:

1.

我们建立一个假的队列,这个队列有队首和队尾,但是没有队列元素。
现在我们从f[i-1][0]向f[i-1][j]每隔w[i]个将那个数添加到队列中,用队列记录队首到队尾的和。这样对于f[i][j],队列中的所有元素的和就是我们图片中红色格子的和。

2.

不用建立队列,并且将方程的维数降为1维。这时转移方程就是:(f[j]表示达成j容量的方案数。)

这就是完全背包的做法再减去不应该装的物品的做法。程序结束后f[i]数组里留下来的就是达成i容量的方案数。但是由于第二层循环需要2次,这种方法还是会莫名其妙就TLE。。。

3.

借鉴于第二种方法,我们可以再开辟一个数组s[j]表示f[j]是装了多少件i物品从而变为可行的。总之这样就可以AC

那么我通过此题的代码如下:(应用了诸多卡常技巧)




T2.多重背包 (HDU2191)

题意:

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

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

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




T3.Bank notes(BZOJ1531权限题)

题意:

给定一些面值的硬币和它们的数量,求凑成给定面值的最少硬币数为多少。

单调队列:

经过像T2那样严谨的分析,我们得出:我们需要一个单调队列维护以下单调性:
队列右侧比左侧新进入
队列左侧的元素代表的凑成的硬币数要更少
这样我们就就可以得到一份优美的代码