返回顶部

收藏

python 解决0-1背包问题算法

更多
#!/usr/bin/python
# -*- coding: utf8 -*-
'''
Created on 2011-10-24

@author: AHAN
python 2.7.2
'''

#n个物体的重量(w[0]无用)
w = [0, 2, 2, 6, 5, 4]
#n个物体的价值(p[0]无用)
p = [0, 6, 3, 5, 4, 6]
#计算n的个数
n = len(w) - 1
#背包的载重量
m = 10
#装入背包的物体,元素为True时,对应物体被装入(x[0]无用)
x = [False for raw in range(n + 1)]
v = 0
#optp[i][j]表示在前i个物体中,能够装入载重量为j的背包中的物体的最大价值
optp = [[0 for col in range(m + 1)] for raw in range(n + 1)]

def knapsack_dynamic(w, p, n, m, x):
    #计算optp[i][j]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            optp[i][j] = optp[i - 1][j]
            if (j >= w[i]) and (optp[i - 1][j - w[i]] + p[i] > optp[i - 1][j]):
                optp[i][j] = optp[i - 1][j - w[i]] + p[i]

    #递推装入背包的物体
    j = m
    for i in range(n, 0, -1):
        if optp[i][j] > optp[i - 1][j]:
            x[i] = True
            j = j - w[i]  

    #返回最大价值
    v = optp[n][m]
    return v

print('最大值为:' + str(knapsack_dynamic(w, p, n, m, x)))
print(x[1:])

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

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. 数控小V 发表 2016-02-17 03:14:02 机器学习算法 Python&R 速查表
  2. kaka_ace 发表 2015-03-28 07:38:44 求机器人可用跳跃方式 (Python 代码实现)
  3. 田俊 发表 2015-04-28 15:16:56 Apriori算法简介及实现(python)
  4. furion 发表 2015-04-28 17:02:36 codility之TapeEquilibrium
  5. Yushneng 发表 2016-04-25 13:51:00 可视化图的基本算法
  6. 0X55AA 发表 2014-08-12 07:09:15 pyrasite项目总结为一条命令
  7. Yusheng 发表 2016-06-29 20:16:49 哈夫曼编码 —— Lisp 与 Python 实现
  8. fox64194167 发表 2018-05-27 00:12:22 python 搜索插入位置
  9. Markjour 发表 2013-12-18 02:28:01 用 Python 改写 PHP 加密解密算法 authcode
  10. linux@linux.cn (linu 发表 2015-10-03 01:18:45 八大排序算法的 Python 实现
  11. 0X55AA 发表 2014-05-28 03:33:25 linux系统键盘输入-hook?
  12. mdjhny 发表 2013-02-14 16:00:00 Python 100题第一部分(节选自1-20题)

发表评论