时间:2021-05-22
递归是个好东西,任何具有递归性质的问题通过函数递归调用会变得很简单。一个很复杂的问题,几行代码就能搞定。
最简单的递归问题:现有重量为weight的包,有若干重量分别为W1,W2.....Wn的物品,试问能否从物品中选出若干件而且重量刚好为weight?
weight具体是怎么构成的,有下面两种情况(假设挑选到Wn时,刚好够weight):
1.从Wn-1开始就已经够weight,那weight=W1+W2+......+Wn=W1+W2+......+Wn-1.
2.加上Wn后刚好够weight,那自然地有weight=W1+W2+......+Wn.
上面两种情况一个有解,那问题就有解,于是我们可以把Wi从背包去掉倒退回去看weight的值。
经过一系列倒推,weight的值有下面三种情况:
1. weight刚刚等于0 //说明有解
2.weight<0 //不可能,所以无解
3. weight>0 and没有W了 //也不可能,无解
def knap(weight,weights,n): //weight为包的容量,weights是一个所有重量的表,n为重量数量 if weight==0: return True; if weight<0 or (n<1 and weight>0): return False; if knap(weight-weights[n-1],weights,n-1): //情况 2 print(weights[n-1]) return True if knap(weight,weights,n-1): //情况 1 return True else: return False超级简单吧!!!如果采用动态规划解决,几十行代码要吧。这就12行代码,简单明了!!!
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了Python基于回溯法解决01背包问题。分享给大家供大家参考,具体如下:同样的01背包问题,前面采用动态规划的方法,现在用回溯法解决。回溯法采用深
本文实例讲述了Python基于动态规划算法解决01背包问题。分享给大家供大家参考,具体如下:在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进
本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题。分享给大家供大家参考,具体如下:问题给定N个物品和一个背包。物品i的重量是Wi,其价值位Vi,
本文实例讲述了Python基于贪心算法解决背包问题。分享给大家供大家参考,具体如下:贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择
本文实例讲述了python基于右递归解决八皇后问题的方法。分享给大家供大家参考。具体分析如下:凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求