首页
学习
活动
专区
工具
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

    警惕!机器学习入门阶段易犯的5个错误

    怎样进入机器学习领域没有定式。我们的学习方式都有些许不同,学习的目标也因人而异。 但一个共同的目标就是要能尽快上手。如果这也是你的目标,那么这篇文章为你列举了程序员们在通往机器学习高手道路上常见的五种错误。 1.将机器学习看得高不可攀 机器学习不过是另一堆技术的集合,你可以用它来解决复杂问题。这是一个飞速发展的领域,因此,机器学习的学术交流一般出现在学术期刊及研究生的课本里,让它看起来高不可攀又难于理解。 要想高效掌握机器学习,我们需要转变观念,从技术转到方法,由精确变为“足够好”,这也同样适用于程序员感兴

    06
    领券