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

相关文章

如何将 awk 脚本移植到 Python

将一个 awk 脚本移植到 Python 主要在于代码风格而不是转译。 脚本是解决问题的有效方法,而 awk 是编写脚本的出色语言。它特别擅长于简单的文本处理,它可以带你完成配置文件的某...

python snownlp情感分析简易demo(分享)

python snownlp情感分析简易demo(分享)

SnowNLP是国人开发的python类库,可以方便的处理中文文本内容,是受到了TextBlob的启发而写的,由于现在大部分的自然语言处理库基本都是针对英文的,于是写了一个方便处理中文的...

浅谈Python peewee 使用经验

本文使用案例是基于 python2.7 实现 以下内容均为个人使用 peewee 的经验和遇到的坑,不会涉及过多的基本操作。所以,没有使用过 peewee,可以先阅读文档 正确性和覆盖面...

pow在python中的含义及用法

pow()方法返回xy(x的y次方) 的值 语法 以下是math模块pow()方法的语法: import math math.pow( x, y ) 内置的pow()方法 p...

Python的Django框架使用入门指引

Python的Django框架使用入门指引

 前言 传统 Web 开发方式常常需要编写繁琐乏味的重复性代码,不仅页面表现与逻辑实现的代码混杂在一起,而且代码编写效率不高。对于开发者来说,选择一个功能强大并且操作简洁的开发...