经过小编这几天冒着挂科的风险,日日修炼,终于赶在考试周中又给大家更新了一篇干货文章。关于用变邻域搜索解决0-1背包问题的代码。怎样,大家有没有很感动?
0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 w_i,其价值为 v_i 。 问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?
为什么叫0-1背包问题呢?显然,面对每个物品,我们只有选择拿取或者不拿两种选择,不能选择装入某物品的一部分,也不能装入同一物品多次。拿就是1,不拿就是0。因此,就叫0-1背包问题。So simple, so naive.
下面就几个邻域小动作给大家讲解一下。
假设我们面前有n种物品,那么我们可以将解决方案设置成一个一维数组selectionn。数组weightsn表示重量,数组valuesn表示价值。
将解决方案selectionn的第i位取反(i=1,2,3,4……n)。比如:
有方案0010,那么生成的邻居解则有1010(第一位取反)、0110(第二位取反)、0000(第三位取反)、0011(第四位取反)。
不知道这么通俗易懂的大家understand了没有。
对于解决方案selectionn,在第i (i=1,2,3,4……n)位取反的情况下,依次将第j (j=i+1,2,3,4……n)位也取反。还是for 一个 example吧。
对于解决方案0010。产生的邻居解如下:
交换第i位和第i-3位的数。如果i<3。就交换最后的,比如:
这个比较简单,随机取反一些位就行了。
下面上代码啦!欲直接下载代码文件,关注我们的公众号哦!回复【VNSKP】即可,不包括【】哦
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。