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

    最简单粗暴的成为大神的可行性方法

    成为万众瞩目的技术大神,是所有程序员的梦想,毕竟,谁不想成为人群中那颗万众瞩目的明星?谁不想每次在大家束手无策的时候,挽狂澜于既倒,扶大厦之将倾?谁不想解决一个刁钻古怪的问题之后,在大家崇拜的目光中,事了拂衣去,深藏功与名? 确实,存在着一些幸运儿,天赋异禀,具有很强的计算能力、记忆能力和推理能力,对数学、计算机都手到擒来,吾辈要钻研很久的东西,对于他们来说,都是显而易见,探囊取物,他们只要稍加努力,自然就是值得顶礼膜拜的大神,是属于金字塔塔尖的那群人。 不过日光之下,并无新事,以广大人民群众努力程度之

    07
    领券