Python动态背包问题，怎么解决
1个回答
2017-11-11 · 百度知道合伙人官方认证企业
育知同创教育
1【专注：Python+人工智能|Java大数据|HTML5培训】 2【免费提供名师直播课堂、公开课及视频教程】 3【地址：北京市昌平区三旗百汇物美大卖场2层，微信公众号：yuzhitc】
向TA提问
关注
![]()
展开全部
def bag(n,c,w,v):
res=[[-1 for j in range(c+1)] for i in range(n+1)]
for j in range(c+1):
res[0][j]=0
for i in range(1,n+1):
for j in range(1,c+1):
res[i][j]=res[i-1][j]
if j>=w[i-1] and res[i][j]<res[i-1][j-w[i-1]]+v[i-1]:
res[i][j]=res[i-1][j-w[i-1]]+v[i-1]
print res
return res
def show(n,c,w,res):
print '最大价值为:',res[n][c]
x=[False for i in range(n)]
j=c
for i in range(n,0,-1):
if res[i][j]>res[i-1][j]:
x[i-1]=True
j-=w[i-1]
print('选择的物品为:')
for i in range(n):
if x[i]:
print '第',i,'个,'
print('')
if __name__=='__main__':
n=5
c=10
w=[2,2,6,5,4]
v=[6,3,5,7,6]
res=bag(n,c,w,v)
show(n,c,w,res)
输出：[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [-1, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6], [-1, 0, 6, 6, 9, 9, 9, 9, 9, 9, 9], [-1, 0, 6, 6, 9, 9, 9, 9, 11, 11, 14], [-1, 0, 6, 6, 9, 9, 9, 13, 13, 16, 16], [-1, 0, 6, 6, 9, 9, 12, 13, 15, 16, 16]]
最大价值为: 16
选择的物品为:
第 0 个,
第 1 个,
第 3 个,
本回答由网友推荐
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
