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

yipeiwu_com6年前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设计】。

相关文章

Linux下python与C++使用dlib实现人脸检测

Linux下python与C++使用dlib实现人脸检测

python 与 C++ dlib人脸检测结果对比,供大家参考,具体内容如下 说明: 由于项目需求发现Linux下c++使用dlib进行人脸检测和python使用dlib检测,得到的结果...

基于python的Paxos算法实现

基于python的Paxos算法实现

理解一个算法最快,最深刻的做法,我觉着可能是自己手动实现,虽然项目中不用自己实现,有已经封装好的算法库,供我们调用,我觉着还是有必要自己亲自实践一下。 这里首先说明一下,python这种...

python 使用pdfminer3k 读取PDF文档的例子

python 使用pdfminer3k 读取PDF文档的例子

1、安装 pdfminer3k 通过pip安装: pip install pdfminer3k 下载安装:在网页 https://pypi.org/project/pdfminer3k/...

python中django框架通过正则搜索页面上email地址的方法

本文实例讲述了python中django框架通过正则搜索页面上email地址的方法。分享给大家供大家参考。具体实现方法如下: import re from django.shortc...

代码分析Python地图坐标转换

最近做项目正好需要坐标的转换 各地图API坐标系统比较与转换; WGS84坐标系:即地球坐标系,国际上通用的坐标系。设备一般包含GPS芯片或者北斗芯片获取的经纬度为WGS84地...