首页 > 代码库 > 动态规划法——求解0-1背包问题

动态规划法——求解0-1背包问题



 问题描述





0-1背包问题与背包问题(贪心法——背包问题)最大的不同就是背包问题的子问题彼此之间没有联系,所以只要找出解决方法,然后用贪心算法,取得局部最优解就ok了,但是0-1背包问题更复杂,因为物品不可再分,导致了子问题之间是有联系的。



问题分析



      1,刻画背包问题最优解的结构




    

        2,数学描述




   

伪代码解读



 


当上段代码运算完成之后,对于C[i,w]的表:



然后根据上面构造的表,求最优解:








  小结


     动态规划法在判断是否含有第i个物品时,通过判断C[I,w]是否等于C[i-1,w]来得出是否含有第i个物品,感觉挺巧妙的,不过前面构造C[I,w]表的过程感觉工程量好大啊。









动态规划法——求解0-1背包问题