初学DP(3.5) – 完全背包 – Luogu P1616 疯狂的采药

完全背包 我们先来回顾一下 01 背包

针对于有一定空间,一定数量的物品,每个物品只能放一个,我们可以把他当为 01 背包,它的状态转移方程是:
f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] )
那么什么是完全背包呢? 针对于有一定空间,一定数量的物品,每个物品能放无数个的背包,我们称其为完全背包, 我们曾经在 初学DP (1) – 01 背包 – 装箱问题 & NOIP 2005 普及 第三题 采药 中提到过 01 背包的 j 循环 这层循环如果从小到大,你们他就会按个累加,那么也就是说把 j 循环从小到大,它,就变成了完全背包

疯狂的采药

这道题中他很明显的说了他和采药的不同点:
1.每种草药可以无限制地疯狂采摘。 2.药的种类眼花缭乱,采药时间好长好长啊!师傅等得菊花都谢了!
那tm不久是完全背包吗!!!!!! 所以你把采药的 j 循环倒一下,数组开大点,AC!!! ]]>

留下评论

电子邮件地址不会被公开。 必填项已用*标注