当前位置: 首页 > 编程笔记 >

C#用递归算法解决经典背包问题

郤仰岳
2023-03-14
本文向大家介绍C#用递归算法解决经典背包问题,包括了C#用递归算法解决经典背包问题的使用技巧和注意事项,需要的朋友参考一下

1.引子

  我们人类是一种贪婪的动物,如果给您一个容量一定的背包和一些大小不一的物品,裝到背包里面的物品就归您,遇到这种好事大家一定不会错过,用力塞不一定是最好的办法,用脑子才行,下面就教您如何解决这样的问题,以获得更多的奖品。

2.应用场景

  在一个物品向量中找到一个子集满足条件如下 :

  1)这个子集加起来的体积大小不能大于指定阀值

  2)这个物品子集加起来价值大小是向量V中所有满足条件1的子集中最大的

3.分析

  背包问题有好多版本,本文只研究0/1版本,即对一个物体要么选用,要么就抛弃,不能将一个物体再继续细分的情况。这种问题最简单的方法就是找出这个向量的所有子集,如同找出幂集中的子集一样,但这种遍历的方法恐怕并不会被聪明的我们所使用,现在举办这些活动的电视台也非常聪明,他们不但要求您能将物品装进去,而且指定操作时间,这样当您慢慢腾腾的装进去倒出来的时候,时间恐怕早就到了,最终您可能一无所获,这可不是我们希望的结果,我们需要使用一些策略:第一次我们可以从大小小于背包容量的物品中随意挑取一个,这样可以尽量争取时间,选取第一个后的每一个我们希望其都是最优的,这样能节省一定的时间。假设有这么一组物品,其大小和价值如下表所示:

物品编号 大小 价值
1 2 1
2 3 4
3 4 3
4 5 6
5 6 8

给我们一个容量为12的背包,让我们装上面这些物品,我们可以用下面的方法来解决寻找最优组合的问题

建立一个二围数组,数组包括n个行(n为物品数量)和capcity+1列

首先我们对第一个物品进行取舍,因为物品1大小为2,先将物品1加入背包,物品1的大小为2,则cap>=2的时候能容纳item1,这时候背包里面物品的价值为item1.Value=1,得到以下数组

0 1 2 3 4 5 6 7 8 9 10 11 12
0 0 1 1 1 1 1 1 1 1 1 1 1

接下来处理物品1和物品2的子集,item2的大小为3,则只有cap=3的时候才能容纳item2,当cap=3的时候讲好能容纳item2,此时背包里面价值item2.value=4,且剩余空间为0,当cap=4的时候,能容纳item2,且剩余空间为1,不能容item1,当cap=5的时候,可以容纳item1+item2,此时的价值为1+4 =5,得到第二行

0 1 2 3 4 5 6 7 8 9 10 11 12
0 0 1 4 4 5 5 5 5 5 5 5 5

下面分析物品三,物品二,物品一的子集,物品三的大小为4,当cap=4的时候就能容纳item3,但此时背包里面的价值为3,明显小于上一行中的cap=4的价值(3<4),所以cap=4时不能将item3放进去,所以第三行的4位置应该和第二行的4位置一致,当cap=5的时候能够容纳item3,且剩余空间为1,和cap=4情况一样,拷贝上一行同一位置的值,当cap=6,放置item3后剩余2,能容item1和item4,二者的总价值:1+3=4<5,故拷贝上一行同位置的值,cap=7的时候,能容item2+item3,总价值大小为7,大于>5,故cap=8的时的值为7,cap=9的时候仍能容难item3+item2,value=7,cap=8的时候,能容纳item1+item2+item3,且总价值大小为8,大于上一行同位置的值,故cap>=9时候,总价值大小为8,第三行:

0 1 2 3 4 5 6 7 8 9 10 11 12
0 0 1 4 4 5 5 7 7 8 8 8 8

按照这样的逻辑可以得到下面两列,最后二围数组是

0,0,1,1,1,1,1,1,1,1,1,1,1

0,0,1,4,4,5,5,5,5,5,5,5,5

0,0,1,4,4,5,5,7,7,8,8,8,8

0,0,1,4,4,6,6,7,10,10,11,11,13

0,0,1,4,4,6,8,8,10,12,12,14,14

得到这样的数组之后,我们需要作的是根据这个二围数组来产生最优物品子集,方法为

从第len行开始,比较最后一行cap索引位置的值是否大于上一行同一位置的值,如先比较第五行位置12的值(14)与第四行位置12的值(13),因为14!=13,所以item5放置到最优集合中,item5的大小为6,故比较第四行cap-6=6的位置上的值与上一行同一位置上值得大小,因为6!= 5,所以item4能放置到最优集合,下一步要比较的位置cap = 6-item4.Size=6-5=1,第三行位置1与第二行位置1相同,故item3不能放置到最优集合,第二行和第一行第一个位置上的值也一样,所以item2也不能放置进去,最后判断item1是否应该在最优集合,item5+item4后,剩余空间为1,不能容纳item1,故最优集合为{item4,item5};

综合上面的分析,我们可以得到这样的一个处理流程

1)首先建立一个nx(cap+1)的二围数组

2)第一行从尝试选择第一个物品开始

3)对于以后的行,对于每个容量1<=cap<=capacity,首先拷贝上一行同一位置的值下来,如果itemi.Size<=cap并且上一行(cap-itemi.Size)位置上的值与itemi.Value的 和(tempMax)大于拷贝下来的值的话,就将拷贝下来的值替换为上一行(cap-itemi.Size)位置上的值与itemi.Value的 和(tempMax)

4)得到完整数组之后,我们既可以根据数组来确定最优集合了,首先从最后一样最后位置开始,和上一行的同一位置进行比较,如果相同,则该行对应索引的物品不能放到背包中,否则放到背包,并且开始比较上一行与 上上一行在当前背包剩余空间索引出的值,如不等,则对应物品可放置,如此,直到处理到第二行和第一行的比对完成,然后根据当前背包剩余容量与第一个物品的大小比对来确定物品一是否能放置到背包中

4.源程序
http://xiazai.jb51.net/201606/yuanma/Knapsack(jb51.net).rar

5.结论

  上文采用的是动态编程的方法来处理此类背包问题,上面的文章中兄弟们也提到了用递归算法时间复杂度的问题,认为递归算法效率比较低下,这种疑问无可厚非,但递归算法也有它的优点,很多问题都能用递归来解决,我目前学习的就是用这种算法来解决一些常见问题,对于其他算法,比如此问题也可以采用贪婪算法,遗传算法等得以更好的解决,但本文暂不作讨论,以后有时间,一定将这些算法加以实现并详细比较其优劣。

 类似资料:
  • 我试图在Scala中使用递归来解决背包问题,但我的要求是显示选择哪些项目保存在背包中。表示背包大小。 我的代码如下: 如何知道选择哪些物品放在背包里?

  • 本文向大家介绍C#用递归算法解决八皇后问题,包括了C#用递归算法解决八皇后问题的使用技巧和注意事项,需要的朋友参考一下 1.引子   中国有一句古话,叫做“不撞南墙不回头",生动的说明了一个人的固执,有点贬义,但是在软件编程中,这种思路确是一种解决问题最简单的算法,它通过一种类似于蛮干的思路,一步一步地往前走,每走一步都更靠近目标结果一些,直到遇到障碍物,我们才考虑往回走。然后再继续尝试向前。通过

  • 本文向大家介绍Java递归算法经典实例(经典兔子问题),包括了Java递归算法经典实例(经典兔子问题)的使用技巧和注意事项,需要的朋友参考一下 题目:古典问题:3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 分析:首先我们要明白题目的意思指的是每个月的兔子总对数;假设将兔子分为小中大三种,兔子从出生后三个月后每个月就会生出一对兔子,

  • 本文向大家介绍Java使用递归解决算法问题的实例讲解,包括了Java使用递归解决算法问题的实例讲解的使用技巧和注意事项,需要的朋友参考一下 解释:程序调用自身的编程技巧叫做递归。 程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模

  • 我想做一个递归算法来解决做出改变的问题。是否可以使用非动态方法,不仅返回最小数量的硬币,还返回用于构成给定值的硬币集, 例如,给定值6和硬币组=[1,3,4]。有没有可能创建一个不记忆的递归算法,可以返回最小数量的硬币(2)和硬币集(3,3)? 编辑:这是我当前的算法,但它只返回硬币总数: 将返回3,但我希望它也提供集合{5,5,1}。第二个参数(2)是硬币的数量减去1。

  • 在我为0/1背包和无界背包签出的所有DP解决方案中,解决方案方法总是这样定义的: 0/1背包:取第n项或不取第n项,使总价值最大化。例如,0/1背包 无界背包:将第n个物品视为最后挑选的物品,或(n-1)个物品视为最后挑选的物品,使总价值最大化。例如,无界背包 但无界背包也可以使用0/1背包的逻辑来解决,只需稍加调整。我的意思是,对于0/1背包,我们执行以下操作(使用第一个链接中的代码): 请注意