注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

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

python 水墨上仙 2611次浏览 已收录 手机上查看

问题:给定一个载重量为m的背包,以及n个重量为wi、价值为pi的物体,1<=i<=n,要求把物体装入背包,使背包内的物体价值最大,把这类问题称为背包问题。通常称物体不可分割的背包问题为0/1背包问题。这个问题也可以用动态规划的分阶段决策方法,来确定把哪一个物体装入背包的最优决策。类似于资源分配那样,令optp[i][j]表示在前i个物体中,能够装入载重量为j的背包中的物体的最大价值,j=1,2,…,m。可以得到下面的动态规划函数:optp[i][0] = optp[0][j] = 0………………………………………..(1)optp[i][j] = optp[i - 1][j] (j < wi)…………………………………(2)optp[i][j] = max{optp[i - 1][j], optp[I - 1][j - wi] + pi}(j >= wi)…(3)式(1)表示,把前面i物体装入载重量为0的背包,或者把0个物体装入载重量为j的背包,得到的价值都为0。(2)式表明,如果第i个物体的重量大于背包的载重量,则装入前面i个物体得到的最大价值,与装入前面i – 1个物体得到的最大价值一样(第i个物体没有装入背包)。式(3)表明,当第i个物体的重量小于背包的载重量时,如果把第i个物体装入载重量为j的背包后总价值上升,那么就装入,否则不装入。

#!/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-1背包问题算法
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……