本人文档均来源于网络如有侵權，请留言本人第一时间删除，对此造成的影响还望见谅。

有N件物品和一个容量为V的背包苐i件物品的重量是w[i]，价值是v[i]求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大在选择装入背包的物品时，对于每种物品i只能选择装包或不装包，不能装入多次也不能部分装入，因此成为0-1背包问题

设最优值m(i,j)为背包容量为j、可选择物品为i，i+1……，n时的最优值(装入包的最大价值)所以原问题的解为m(1，C)

将原问题分解为其子结构来求解要求原问题的解m(1，C)可从m(n，C)m(n-1，C)m(n-2，C).....来依次求解即可装包物品分别为（物品n）、（物品n-1，n）、（物品n-2n-1，n）、……、（物品1物品2，……物品n-1物品n）。最后求出的值即為最优值m(1C)。

若求m(i,j)此时已经求出m(i+1,j)，即第i+1个物品放入和不放入时这二者的最大值

对于此时背包剩余容量 j=0,1,2,3……C，分两种情况：

(2)当 w[i] <= j 即第i个粅品重量不大于背包容量j时，这时要判断物品i放入和不放入对m的影响

　　　　　　　　若不放入物品i，则此时m(i,j)=m(i+1,j)

总结得出状态转移方程为：

该算法的python代码实现：

但是但是！！该算法有两个明显的缺点：1，基于上述代码因为数组索引的需要，要求所给物品重量为整数2，當背包容量C很大时算法所需计算时间较多。当C>2^n时需要Ω(n*2^n)计算时间。

所以所以！！改进算法如下：

对于函数m(i,j)的值，当i确定j为自变量時，是单调不减的跳跃式增长如图所示。而这些跳跃点取决于在（物品i物品i+1，……物品n）中选择放入哪些物品使得在放入重量小于容量 j (0<=j<=C)的情况下m取得最大值对于每一个确定的i值，都有一个对应的跳跃点集Pi={

)……}，在函数图像上表现为所有跳跃点横轴坐标右移w[i-1]纵轴坐標上移v[i-1]。

(3)求Pi-1即求Pi∪Qi然后再去掉受控跳跃点后的点集。此处有个受控跳跃点的概念：若点(a,b)(c,d)∈Pi∪Qi，且a<=cb>d，则(c,d)受控于(a,b)所以(c,d)?Pi-1。去掉受控跳躍点是为了求得在物品i-1放入后m较大的点，即 使m取最优值的跳跃点

由此计算得出Pn，Pn-1……，P1求得P1的最后那个跳跃点即为所求的最优值m(1,C)。

最后python代码的实现：