如何用Python推导01背包问题的完整思维过程？

本文共计441个文字，预计阅读时间需要2分钟。

文章目录+ 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])

the executed result:

01背包问题的推演过程

关于自底向上

tips:我们考虑从子问题的角度求解:

(往往需要理想化一些条件来使用(比如假设我们有现成的所有子问题规模的下的最优解),基于这样的条件来推导状态方程:

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