0/1背包问题Python实现 _阿- c 实现背包问题

问题:给定一个载重量为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的背包后总价值上升,那么就装入,否则不装入。

算法实现如下(Python编写,经测试可用):

#!/usr/bin/python

#-*-coding:utf8-*-

'''

Createdon2011-10-24

@author:AHAN

python2.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]无用)

0/1背包问题(Python实现)_阿- c 实现背包问题

x=[Falseforrawinrange(n+1)]

v=0

#optp[i][j]表示在前i个物体中,能够装入载重量为j的背包中的物体的最大价值

optp=[[0forcolinrange(m+1)]forrawinrange(n+1)]

defknapsack_dynamic(w,p,n,m,x):

#计算optp[i][j]

foriinrange(1,n+1):

forjinrange(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

foriinrange(n,0,-1):

ifoptp[i][j]>optp[i-1][j]:

x[i]=True

j=j-w[i]

#返回最大价值

v=optp[n][m]

returnv

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

print(x[1:])

  

爱华网本文地址 » http://www.413yy.cn/a/25101013/157784.html

更多阅读

iOS5.0.1完美越狱教程图文完整版 局长日记完整版图文

ios5终于完美越狱啦,想必大家都等很久啦,所有非A5处理器的ios设备升级到ios5.0.1均可实现完美越狱。以下教程就是教大家怎么完美越狱,最重要的是,越狱之后使用同步助手,就可以不需要装appsync补丁哦。支持iOS5.0.1完美越狱支持机型(不支持

Myeclipse6.0.1注册码获取方法 myeclipse注册码

Myeclipse6.0.1注册码获取方法——简介Myeclipse是编程者熟知的编程软件,但是因为需要注册,这里告诉大家如何获取Myeclipse6.0.1版本注册码。Myeclipse6.0.1注册码获取方法——工具/原料Myeclipse6.0.1Myeclipse6.0.1注册码获取方法

192.168.0.1无法打开怎么办 精 无法打开192.168.0.1

192.168.0.1无法打开怎么办 精——简介默认情况下,登陆路由器管理界面的地址是192.168.0.1或192.168.1.1。当我们输入以上网址去无法进入管理界面时,你是否曾一筹莫展过。今天小编就给大家支几招解决之法,希望对需要的朋友有所帮助。1

192.168.1.1路由器打不开怎么办? 192.168.0.1路由器

朋友新买一台笔记电脑,为笔记本设置无线上网时要进入路由器,在浏览器中输入192.168.1.1 路由器却打不开的问题,具体表现为访问路由器IP(通常是http://192.168.1.1或http://192.168.0.1)但却打不开网页,这到底是什么原因呢?192.168.1.1路由

声明:《0/1背包问题Python实现 _阿- c 实现背包问题》为网友穿着凉鞋闯江湖分享!如侵犯到您的合法权益请联系我们删除