0－1背包问题–动态规划

问题描述：
给定一个物品集合s＝｛1，2，3，…，n｝，物品i的重量是wi，其价值是vi，背包的容量为W，即最大载重量不超过W。在限定的总重量W内，我们如何选择物品，才能使得物品的总价值最大。如果物品不能被分割，即物品i要么整个地选取，要么不选取；不能将物品i装入背包多次，也不能只装入部分物品i，则该问题称为0—1背包问题。如果物品可以拆分，则问题称为背包问题，适合使用贪心算法。
算法分析： 假设xi表示物品i装入背包的情况，xi＝0，1。
当xi＝0时，表示物品没有装入背包；当xi＝1时，表示把物品装入背包。 因此问题就归结为找到一个满足上述约束方程，并使目标函数达到最大的解向量： X＝{x1，x2，…，xn},
递归关系分析：
0—1背包问题具有最优子结构性质，设所给0—1背包问题的子问题：

i≤k≤n的最优值为p(i，j)。 是背包容量为j，可选物品为i，i＋1，…，n时0-1背包问题

0－1背包问题–动态规划最先出现在Python成神之路。