在前两篇文章中,我们仔细讨论了01背包问题和完全背包问题。在本文中,我们将介绍另一个背包问题-多背包问题。多背包问题的项数介于01背包问题和完全背包问题之间,项数是有限的!
有各种各样的物品和一个背包,容量为。第三项的数量不超过几件。每件物品的体积为,价值为。解决哪些物品装入背包可以使物品的总体积不超过背包的容量,总价值最大。
注:上述字符在本文中的含义相同。
多背包问题与01背包和完整背包的区别在于,01背包只能使用一次,多背包可以使用无数次,而多背包可以多次使用。
01在背包问题中,我们使用二维数组进行计算,这表明当仅使用第一件物品且背包容量为时,我们可以获得最大利润。在这种情况下,通过根据当前背包容量判断物品是否可以装载,我们可以得到以下两个等式:
上面01背包公式的第二项相对简单。如果背包容量不足以容纳第一件物品,您只能从之前的物品中进行选择。让我们仔细分析第一个公式。
如果当前背包容量可以容纳该物品,则我们可以选择该物品或不选择该物品。
[新闻热点]
我们应该在两种选择中选择利润更大的一种。如果我们不选择第一件物品,我们可以使用有容量的背包来选择第一件。在这种情况下,我们的最大利润是。
如果您选择了该项目,那么我们仍然有背包容量,您可以选择剩余的项目,我们的收入需要增加,因此我们的收入是。
在多个背包的问题中,我们可以使用一件物品的次数多于三次。事实上,我们可以将多个背包转换为01个背包。例如,我们可以将三个项目更改为三个不同的项目。所谓的差异是它们的名称不同,但它们的值和体积相同。假设体积为,值为,可以使用的次数为3,我们可以将它们转换为,,,这三项的体积和值都是,这样,它可以转换为三次,只能使用一次。通过此转换,我们可以将多个背包转换为01个背包。
多背包代码:
与01背包一样,我们也可以使用单列数组优化多个背包:
当背包容量足够时,01背包的动态传递方程为:
上述动态传递方程基于每个项目的选择和非选择。对于多个背包,如果物品可以选择次数,我们可以选择0次,我们可以选1次,…,我们可以选择时间,我们需要选择从这些情况中受益最大的一个,因此,多个背包的动态传递方程如下其中,表示可以选择物品的次数,表示物品的体积,表示当前背包的容量:
基于上述动态传递方程,我们可以获得以下代码:
在本文中,我们主要介绍多背包的两种解决方案。一种是将多个背包转换为01个背包,另一种是根据多个背包的动态传递方程求解问题。可以看出,后者具有较低的空间复杂度并节省更多的内存空间。在下一期中,我们将使用另一种方法优化多个背包。
以上是本文的全部内容。我希望你能得到一些东西。我是乐红。下次见!!!
发表评论