python基于递归如何解决背包问题-创新互联
这篇文章主要介绍了python基于递归如何解决背包问题,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
网站建设哪家好,找创新互联建站!专注于网页设计、网站建设、微信开发、小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了内江免费建站欢迎大家使用!递归是个好东西,任何具有递归性质的问题通过函数递归调用会变得很简单。一个很复杂的问题,几行代码就能搞定。
最简单的递归问题:现有重量为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行代码,简单明了!!!
感谢你能够认真阅读完这篇文章,希望小编分享的“python基于递归如何解决背包问题”这篇文章对大家有帮助,同时也希望大家多多支持创新互联,关注创新互联行业资讯频道,更多相关知识等着你来学习!
文章标题:python基于递归如何解决背包问题-创新互联
浏览地址:http://scyanting.com/article/diohci.html