回溯法求解01背包问题解空间树详细分析_01背包问题回溯法如何画解空间树

•  这里我们有一个背包，设置背包的最大承重量为10，再把物品的数量设为w(weight)，价值设为v(value)，当放入物品是x=1，不放入物品时 x=0。                                      

这是一个二叉树，所用到的遍历方式是深度优先遍历

• 1.我们先将背包的物品和重量进行初始化，w=0,v=0起始点就为1。
• 2.我们把第一个物品放入背包中，x=1放入，当前节点向左扩展，此时物品的总重量Cw=2，物品的总价值Cp=6。
• 3.此时物品没有超过背包最大承重量我们将第二个物品放入背包中，x=1放入，当前节点向左扩展，此时物品的总重量Cw=7，物品的总价值Cp=9。
• 4.当我们要放入第四个物品的时候，我们会发现若放入则此时物品的重量超过了背包最大承重量，所以我们考虑不放入的情况，即x=0不放入，当前节点向右扩展，此时物品的总重量和总价值不变我们再考虑第四个物品能不能放入。
• 5.当我们跳过第四个放入第五个物品的时候，我们会发现物品重量不会超过背包最大承重量可以放入，x=1放入，当前节点向左扩展，此时物品的总重量Cw=9，Cp=13，这时候我们就得到了当前情况的最优解Bestp=13。
• 6.当我们算完了第一种情况是我们需要进行回溯，也就是所谓的退栈过程，而之前所遍历的节点我们可以看作是指针指向节点的一个个标记，此时我们根据标记进行回退，当回退到第二个节点时，我们会发现物品可以一另一种方式进入背包，即第二个物品不放入，此时Cw=2，Cp=6，此时我们在考虑第三个物品能不能放入。
• 7.当我们跳过第二个放入第三个物品的时侯，我们会发现物品重量不会超过背包最大承重量可以放入，x=1放入，当前节点向左扩展，此时物品的总重量Cw=6，Cp=11，这时候我们在考虑第四个物品能不能放入。
• 8.当我们放入第四个物品的时候，我们会发现物品重量不会超过背包最大承重量可以放入，x=1放入，当前节点向左扩展，此时物品的总重量Cw=8，Cp=15，此时背包里已经没有物品，我们就得到了最优解Bestp=15
• 9.当我们算完了第二种情况我们同第一次回溯的过程进行回溯，当回溯到第一个节时，我们发现第一个不放入时的价格和最后一个不放入重量相同且最后一个价值更小，所以这里就不进行分析了。

• 从上面可以得出这里bestp最大的是15，选择为第1，3，4物品时背包里总价值最大。