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

yipeiwu_com7年前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模拟鼠标点击实现方法(将通过实例自动化模拟在360浏览器中自动搜索python)

Python模拟鼠标点击实现方法(将通过实例自动化模拟在360浏览器中自动搜索python)

一、准备工作: 安装pywin32,后面开发需要pywin32的支持,否则无法完成与windows层面相关的操作。 pywin32的具体安装及注意事项: 1、整体开发环境: 基于wind...

django输出html内容的实例

最近在学习django,于是就用django做了一个简单的网站,用来练手,具体功能就是从网上抓取数据,然后放到我的网站上面,但是遇到一个问题就是django无法输出html格式的内容,只...

python整合ffmpeg实现视频文件的批量转换

转换工具层出不穷,ffmpeg才是全能的转换工具,只是不支持图形操作。 没有关系,命令行方式,在freebsd/linux下直接来 我们的思路是,设定一个文件夹存放源视频文件,pytho...

如何使用Python标准库进行性能测试

如何使用Python标准库进行性能测试

Profile 和 cProfile 在 Python 标准库里面有两个模块可以用来做性能测试。 1. 一个是 Profile,它是一个纯 Python 的实现,所以会慢一些,如果你需要...

python 生成器生成杨辉三角的方法(必看)

用Python写趣味程序感觉屌屌的,停不下来 #生成器生成展示杨辉三角 #原理是在一个2维数组里展示杨辉三角,空的地方用0,输出时,转化为' ' def yang(line):...