0/1knapsack背包问题:完整思维演推导过程+python

来源：互联网收集：自由互联发布时间：2022-06-14

文章目录 the python code: the executed result: 01背包问题的推演过程关于自底向上 tips:我们考虑从子问题的角度求解: 算法导论习题中伪代码

文章目录

the python code:
the executed result:
01背包问题的推演过程

关于自底向上
tips:我们考虑从子问题的角度求解:

算法导论习题中伪代码及其解释

the python code:

class Item():
def __init__(self,weight,value):
self.value=value
self.weight=weight
# test data:
items_list=[Item(2,3),Item(3,4),Item(1,5),Item(5,6)]
# items_list=[Item(2,3),Item(3,4),Item(1,5),Item(6,26)]

def knapsack01(n, w,items_list):
"""[summary]

Args:
n (int): the number of the items to be choose （originally)
w (int): the max weight the knapsack could maintain
items_list (list): list of items

Returns:
list: two dimesion list (the last element is the max value of the knapsack)
"""
k = [[0 for j in range(w+1)] for i in range(n+1)]

for i in range(1,n+1):
for j in range(1,w+1):
item=items_list[i-1]
if j<item.weight:
k[i][j]=k[i-1][j]
else:
k[i][j]=max(k[i-1][j],k[i-1][j-item.weight]+item.value)
return k

k=knapsack01(4,6,items_list)
for line in k:
print(line)
print("the max value:",k[-1][-1])