回溯法01背包

※※※※只为考试，解释大致意思，如有错误还望海涵！※※※※

有载重量的背包，物体重量分别为5,15,25,27,30，物体价值分别为12,30,44,46,50。求最优装入背包的物体及价值。

1. 为0，计算，大于，生成结点1,2,3,4，部分解(1,1,1,0)；
2. 在结点4计算，大于，继续向下搜索生成结点5，得到价值为86的可行解(1,1,1,0,0)，保存在解向量中， 更新为86；

3. 由叶结点5继续搜索时，被置为86，不大于的值，因此，沿右儿子分支结点回溯到左儿子分支结点3，生成右儿子分支结点6，得到部分解(1,1,0)；
4. 在结点6计算，大于，因此，生成结点7,8,，得到价值为87的可行解(1,1,0,1,0)，更新解向量，更新为87；
5. 由叶结点8继续搜索时，被置为87，不大于的值，因此，沿右儿子分支结点回溯到左儿子分支结点7，生成右儿子分支结点9，得到部分解(1,1,0,0)；
6. 在结点9计算，大于，生成结点10，得到价值为92的可行解(1,1,0,0,1)，更新解向量，更新为92；
7. 由叶结点10继续搜索时，被置为92，不大于的值，因此，进行回溯，因为结点10是左儿子结点，生成右儿子结点11，得到可行解(1,1,0,0,0)；
8. 由叶结点11继续搜索时，被置为42，不大于的值，因此，沿右儿子分支结点回溯到左儿子分支结点2，生成右儿子分支结点12，得到部分解(1,0)；
9. 在结点12计算，小于，因此，回溯到左儿子分支结点1，生成右儿子分支结点13，得到部分解(0)；
10. 在结点13计算，小于，因此，向上回溯到根结点0，结束算法。最后，由向量中的内容，得到最优解(1,1,0,0,1)，从中得到最大价值92。

白话开始，请配合书、PPT和word食用更佳！！！！！

※※※※注意左下角是计算p_est,不是计算p_total※※※※