讨论 / Python2实现(0-1背包问题)
cqulpj 2019-01-09 22:04:27
点我顶贴 收藏 删除
#coding=gbk

# 0-1背包问题求最优解

# n:总钱数

# v:价格列表

# p:重要度列表

def max_value(n, v, p):

# 为了后面计算方便,先在v和p首部插入0

v.insert(0, 0)

p.insert(0, 0)

# 物品数量

m = len(v)

# 初始化最优矩阵

n += 1

F = [[0]*n for i in range(m)]

# 递推最优矩阵

for i in range(1, m):

for j in range(1, n):

if j >= v[i]:

F[i][j] = max(F[i-1][j], F[i-1][j-v[i]]+p[i]*v[i])

else:

F[i][j] = F[i-1][j]

return F[-1][-1]

#主函数

ss = raw_input()

[N, m] = [int(i.strip()) for i in ss.split(' ')]

v = []

p = []

for i in range(m):

ss = raw_input()

[vi, pi] = [int(i.strip()) for i in ss.split(' ')]

v.append(vi)

p.append(pi)

print max_value(N, v, p)

查看更多回复
提交回复