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行代码，简单明了！！！

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python基于回溯法解决01背包问题实例

    Python基于回溯法解决01背包问题实例

    本文实例讲述了Python基于回溯法解决01背包问题.分享给大家供大家参考,具体如下: 同样的01背包问题,前面采用动态规划的方法,现在用回溯法解决.回溯法采用深度优先策略搜索问题的解,不多说,代码如下: bestV=0 curW=0 curV=0 bestx=None def backtrack(i): global bestV,curW,curV,x,bestx if i>=n: if bestV<curV: bestV=curV bestx=x[:] else: if curW+w[i]

  • Python基于贪心算法解决背包问题示例

    本文实例讲述了Python基于贪心算法解决背包问题.分享给大家供大家参考,具体如下: 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解. 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关. 完全背包问题:给定n个物品和一个容量为C的背包,物品i的重量是Wi,其价值为Vi,背包问题是如何选择入背包

  • Python基于动态规划算法解决01背包问题实例

    Python基于动态规划算法解决01背包问题实例

    本文实例讲述了Python基于动态规划算法解决01背包问题.分享给大家供大家参考,具体如下: 在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决.n=5是物品的数量,c=10是书包能承受的重量,w=[2,2,6,5,4]是每个物品的重量,v=[6,3,5,4,6]是每个物品的价值,先把递归的定义写出来: 然后自底向上实现,代码如下: def bag(n,c,w,v): re

  • Python基于回溯法子集树模板解决0-1背包问题实例

    Python基于回溯法子集树模板解决0-1背包问题实例

    本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题.分享给大家供大家参考,具体如下: 问题 给定N个物品和一个背包.物品i的重量是Wi,其价值位Vi ,背包的容量为C.问应该如何选择装入背包的物品,使得放入背包的物品的总价值为最大? 分析 显然,放入背包的物品,是N个物品的所有子集的其中之一.N个物品中每一个物品,都有选择.不选择两种状态.因此,只需要对每一个物品的这两种状态进行遍历. 解是一个长度固定的N元0,1数组. 套用回溯法子集树模板,做起来不要太爽!!! 代码 '''0-

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

    递归是个好东西,任何具有递归性质的问题通过函数递归调用会变得很简单.一个很复杂的问题,几行代码就能搞定. 最简单的递归问题:现有重量为weight的包,有若干重量分别为W1,W2.....Wn的物品,试问能否从物品中选出若干件而且重量刚好为weight? weight具体是怎么构成的,有下面两种情况(假设挑选到Wn时,刚好够weight): 1. 从Wn-1开始就已经够weight,那weight=W1+W2+......+Wn=W1+W2+......+Wn-1. 2.加上Wn后刚好够weig

  • C++回溯与分支限界算法分别解决背包问题详解

    C++回溯与分支限界算法分别解决背包问题详解

    目录 算法思想 回溯代码 分支限界代码 算法思想 分支限界法与回溯法的求解目标不同. 回溯法的求解目标是找出解空间中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解. 由于求解目标不同,导致分支限界法与回溯法对解空间的搜索方式也不相同. 回溯法以深度优先的方式搜索解空间,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间. 回溯法对解空间做深度优先搜索时,有递归回溯和迭代回溯(非

  • Python基于ImageAI实现图像识别详解

    目录 背景简介 图像预测 算法引入 目标检测 图像目标检测 视频目标检测 背景简介 ImageAI是一个面向计算机视觉编程的Python库,支持最先进的机器学习算法.主要图像预测,物体检测,视频对象检测与跟踪等多个应用领域.利用ImageAI,开发人员可用很少的代码构建出具有包含深度学习和计算机视觉功能的应用系统. ImageAI目前支持在ImageNet数据集上对多种不同机器算法进行图像预测和训练,ImageNet数据集项目始于2006年,它是一项持续的研究工作,旨在为世界各地的研究人员提供易

  • 基于Python代码编辑器的选用(详解)

    基于Python代码编辑器的选用(详解)

    Python开发环境配置好了,但发现自带的代码编辑器貌似用着有点不大习惯啊,所以咱们就找一个"好用的"代码编辑器吧,网上搜了一下资料,Python常用的编辑器有如下一些: 1. Sublime Text 2. Vim 3. PyScripter 4. PyCharm 5. Eclipse with PyDev 6. Emacs 7. Komodo Edit 8. Wing 9. The Eric Python IDE 10. Interactive Editor for Python

  • 对Python生成器、装饰器、递归的使用详解

    1.Python生成器表达式 1).Python生成器表达式 语法格式: (expr for iter_var in iterable) (expr for iter_var in iterable ifcond_expr) 2).自定义生成器 函数中使用yield,会返回一个生成器对象.yieldx 生成器使用示例: In [1]:list((i**2 for i in range(1,11))) Out[1]:[1, 4, 9, 16, 25, 36, 49, 64, 81, 100] In

  • 基于python实现雪花算法过程详解

    基于python实现雪花算法过程详解

    这篇文章主要介绍了基于python实现雪花算法过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Snowflake是Twitter提出来的一个算法,其目的是生成一个64bit的整数: 1bit:一般是符号位,不做处理 41bit:用来记录时间戳,这里可以记录69年,如果设置好起始时间比如今年是2018年,那么可以用到2089年,到时候怎么办?要是这个系统能用69年,我相信这个系统早都重构了好多次了. 10bit:10bit用来记录机器ID

  • python爬虫泛滥的解决方法详解

    我们可以把互联网上搬运数据的程序看成小蚂蚁,它们需要采集不同的食物带回洞里存储.但是大家也知道白蚁泛滥的事件,在我们的网络环境里,如果爬虫都集中在某几个位置,最直接的结果就是这个网站的拥挤.对于我们这些网站访问者而言也不是好事情,首先网页的页面会被卡住.网站的管理人员面对爬虫过多,这时候就要进行一系列的限制措施了,这里小编分了两个大的应对方向,从不同的角度进 行分析爬虫过多的解决思路. 一.识别爬虫 1. HTTP请求头 这算是最基础的网络爬虫识别了,正常的网络访问者都是通过浏览器对网站进行访问

  • 基于Python实现简单的定时器详解

    基于Python实现简单的定时器详解

    所谓定时器,是指间隔特定时间执行特定任务的机制.几乎所有的编程语言,都有定时器的实现.比如,Java有util.Timer和util.TimerTask,JavaScript有setInterval和setTimeout,可以实现非常复杂的定时任务处理.然而,牛叉到无所不能的Python,却没有一个像样的定时器,实在令人难以理解. 刚入门的同学一定会说:不是有个time.sleep吗?定好闹钟睡大觉,闹钟一响,起来干活,这不就是一个定时器吗?没错,time.sleep具备定时器的基本要素,但若作

  • 基于Python绘制世界疫情地图详解

    基于Python绘制世界疫情地图详解

    世界疫情数据下载请点击>>:疫情数据下载 注:此数据是2022年3月12号的结果,其中透明的地方代表确诊人数小于10万人,白色的地方代表无该国家的数据. 最终效果: 下载需要的python包: pip install echarts-countries-pypkg pip install echarts-china-provinces-pypkg pip install echarts-countries-china-cities-pypkg import seaborn as sns imp

  • 基于Python实现打哈欠检测详解

    基于Python实现打哈欠检测详解

    目录 效果图 基本思路 部分源码 效果图 基本思路 在 OpenCV 中使用VideoCapture方法初始化视频渲染对象 创建灰度图像 导入预训练模型,识别脸部和人脸标志 计算上唇和下唇距离(其它类似) 创建唇边距离的If条件,满足则是打哈欠,不满足则只是简单的张嘴 显示帧/图像 部分源码 suc, frame = cam.read() # 读取不到退出 if not suc: break # ---------FPS------------# ctime = time.time() fps

随机推荐