首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

动态规划——多重背包

多重背包区别于01背包和完全背包的关键是,物品的个数一定。 但它们的状态方程还是一样的,对于多次背包问题,我们可以把他转换成01背包问题,但是要注意优化,因为当数据量比较大的时候,容易费时,即时间复杂度太高,需要进行优化。 我们先把之前的状态方程在· f[i][j]表示从i个物品中选取体积不超过j物品的最大价值。 f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,........,f[i-1][j-kv]+kw),kv<j。 这时读者朋友可能会想可不可以像完全背包那样,进行状态方程的转换。emmm,答案是:不可以的,不信的话可以自己尝试转换一下。 下面我们用01背包的思想去解决该问题,对于i个物品有k个,价值为w;那么我们可不可以把它这样理解:我们把这些物品都看成不一样的,再仔细想一下,这不就变成01背包了吗?但是时间太慢了,我们优化一下。 这里的优化为二进制优化 我们把这k个物品进行分割处理, 分为1,2,4,8,16………。只要保证其和大于k就可以。 为什么空2进制来优化呢,因为可以减少时间复杂度,其他0到k之中的任意一个数都可以由分割的二进制数进行组合而成。 例如:k为25,下面进行分割 1,2,4,8,16.怎么分割的呢? 先是1,那么还剩24 2,22 4,28 8,20 16,4 4,0//剩余的自己组成一个 剩下就是01背包了,注意此时不再有i个物品了,而是变成了转换以后的物品个数。

04
领券