print(
'请输入待装物品数量和背包体积(空格隔开):'
)
n, v = map(int, input().split())
# 获取物品数量和背包体积
goods = []
# 初始化商品列表
for
i
in
range(n):
print(f
'请输入第{i + 1}个物品的重量和价值(空格隔开):'
)
goods.append(list(map(int, input().split())))
# 获取商品信息
# 计算最优值矩阵
dp = [[0
for
i
in
range(v + 1)]
for
j
in
range(n + 1)]
# 初始化最优值矩阵
for
i
in
range(1, n + 1):
for
j
in
range(1, v + 1):
dp[i][j] = dp[i - 1][j]
# 默认不装,即和上一项最优值相等
if
j >= goods[i - 1][0]:
# 如果背包剩余空间充足
dp[i][j] = max(dp[i][j], dp[i - 1][j - goods[i - 1][0]] +
goods[i - 1][1])
# 对比装与不装的价值并选择较大值
""
"
# 输出最优值矩阵
for i in dp:
print(i)
"
""
# 计算最优解
x = [0
for
i
in
range(n + 1)]
# 初始化物品状态,0:不装,1:装
for
i
in
range(n, 0, -1):
if
dp[i][v] == dp[i - 1][v]:
# 判断最优值是否发生变化,如果没有变化,则说明没有装
x[i] = 0
# 不装
else
:
# 如果有变化,则说明装了,并减去对应重量
x[i] = 1
# 装
v -= goods[i - 1][0]
# 减去对应重量
x[n] = 1
if
dp[n][v] != 0
else
0
# 判断最后一个物品装不装
# 输出最优解
print(
'背包应装物品为:'
)
for
i
in
range(1, n + 1):
print(f
'编号:{str(i)}\t重量:{goods[i - 1][0]}\t价值:{goods[i - 1][1]}\n'
if
x[i] == 1
else
''
, end=
''
)
# 输出最优值
print(
'物品价值:'
, dp[-1][-1])