关于
联系
本站已运行
载入天数...载入时分秒...
本站 CDN 服务由 提供
Woshiluo's Notebook
初学DP(4) – 多重背包及其优化 – Codevs 3269
2018年2月11日 / 周日 / 0 条评论

多重背包 我们曾经说过完全背包和01背包,但是这两个方法都有一个问题,就是物件个数都是一致的并且是确定的,但如果他不确定呢? 我们可以定义一个k循环来模拟他的件数,不过显然这样做的华时间复杂度会超过我们的想象 所以我们需要进行优化,优化的方式有两种 二进制优化 单调队列 二进制优化 我们来观察下面这几 ...
 


完全背包 我们先来回顾一下 01 背包 针对于有一定空间,一定数量的物品,每个物品只能放一个,我们可以把他当为 01 背包,它的状态转移方程是: f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] ) 那么什么是完全背包呢? 针对于有一定空间,一定数量的物品,每个物品能放无数个的背包,我们称其为完全背包, 我们曾经 ...
 



<