返回顶部

收藏

python递归解决0-1背包问题

更多
#coding:utf-8
#递归实现的背包算法
#背包大小
bag=10
#物品大小清单
list=[5,9,8,2,4,1,6,7,3]
#预处理:从小到大排序
list.sort()
#求背包组合
def getb(B,L):
    #本次查找结果
    r=[]
    #取最小数
    for k in range(0,len(L)):
        #去掉前面的k-1个元素,组成sL列表,在此基础上查找,以免出现重复的组合
        sL=L[k:]
        if len(sL)<2:
            break
        #取第一个元素(列表中的最小元素)
        x=sL[0]
        #背包的剩余空间
        e=B-x
        #查找e是否在表中,从sL[1]开始查找
        for i in range(1,len(sL)):
            #找到等于e的值,存入这组结果
            if sL[i]==e:
                r.append([x,sL[i]])
                break
            elif sL[i]>e:
                break
        #取子列表,sL[i]>=e的情况取中间的片段(减少不必要的开销),否则取从1开始的全部片段
        if sL[i]>=e:
            sL=sL[1:i]
        else:
            sL=sL[1:]
        #继续在子列表sL[1:]中以e为背包大小求组合
        sr=getb(e,sL)
        #查找的子结果处理后添加到结果列表中
        for j in sr:
            j.insert(0,x)
        r.extend(sr)
    #返回本次查找结果
    return r
#计算结果,输出结果
result=getb(bag,list)
for i in result:
    print i

输出结果: [1, 9] [1, 2, 7] [1, 2, 3, 4] [1, 3, 6] [1, 4, 5] [2, 8] [2, 3, 5] [3, 7] [4, 6]

标签:背包问题,算法,python

收藏

0人收藏

支持

1

反对

0

相关聚客文章
  1. 姚 广远 发表 2015-06-19 00:23:25 用Python实现各种排序算法
  2. 博主 发表 2012-02-29 23:24:00 AStar算法的python实现
  3. 0X55AA 发表 2014-07-22 13:23:03 whitespace的python实现
  4. 小数点 发表 2017-04-18 02:43:37 python学习之路——python切片模拟LRU算法
  5. fox64194167 发表 2018-05-27 00:12:22 python 搜索插入位置
  6. master 发表 2015-09-27 23:31:38 校园招聘的简单总结
  7. LinkinPark 发表 2015-10-01 15:09:41 互联网和金融 在数据挖掘上究竟存在什么区别?
  8. MitchellChu 发表 2015-11-08 07:51:45 Python产生token唯一值的算法性能比较
  9. 田俊 发表 2014-09-10 11:32:42 Apriori算法简介及实现(python)
  10. fox64194167 发表 2018-05-26 23:53:35 python 寻找重复的数
  11. 数控小V 发表 2016-02-17 03:14:02 机器学习算法 Python&R 速查表
  12. Yusheng 发表 2016-06-29 20:16:49 哈夫曼编码 —— Lisp 与 Python 实现