python基于递归解决背包问题详解

yipeiwu_com5年前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使用dis模块把Python反编译为字节码的用法详解

dis — Disassembler for Python bytecode,即把python代码反汇编为字节码指令. 使用超级简单: python -m dis xxx.py...

python实现mysql的读写分离及负载均衡

python实现mysql的读写分离及负载均衡

Oracle数据库有其公司开发的配套rac来实现负载均衡,目前已知的最大节点数能到128个,但是其带来的维护成本无疑是很高的,并且rac的稳定性也并不是特别理想,尤其是节点很多的时候。...

python3获取当前目录的实现方法

1. 以前的方法 如果是要获得程序运行的当前目录所在位置,那么可以使用os模块的os.getcwd()函数。 如果是要获得当前执行的脚本的所在目录位置,那么需要使用sys模块的sys.p...

在Python下进行UDP网络编程的教程

在Python下进行UDP网络编程的教程

TCP是建立可靠连接,并且通信双方都可以以流的形式发送数据。相对TCP,UDP则是面向无连接的协议。 使用UDP协议时,不需要建立连接,只需要知道对方的IP地址和端口号,就可以直接发数据...

Django中多种重定向方法使用详解

前言 本文使用了Django1.8.2 使用场景,例如在表单一中提交数据后,需要返回到另一个指定的页面即可使用重定向方法 一、 使用HttpResponseRedirect fu...