python基于递归解决背包问题详解_贪心算法背包问题详解,python递归解决背包问题 - CSDN文库

解决背包问题

1星 153 浏览量更新于2023-03-16 评论 1 收藏 39KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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

主要介绍了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页未读，立即下载

评论1

qq_30841973

2021-03-30

看到pdf瞬间没有下载的欲望了

weixin_38590456

粉丝: 1
资源: 884

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈