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

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

文章目录

​​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

the executed result:

01背包问题的推演过程

关于自底向上

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

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。