本人此时还是一名研一的小菜鸡，刚学会了这个算法的基本概念，来总结一下，谁知道今后的我再看到这篇自己写的博客的时候会不会笑出来，哈哈哈哈哈哈哈哈，所以吗，错了的化大佬们评论指正就好了。
还有系列文章动态规划法解01背包问题，分支限界法解01背包问题哈，需要的化以下是链接：
动态规划法：https://blog.csdn.net/_/article/details/
分支限界法：https://blog.csdn.net/_/article/details/
1背包问题题干（题目中所给出的条件和问题）
给定n种物品和一背包。物品i的体积是Si，其价值为Vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
2回溯法求解
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
粘一段百度百科的内容作为概念解释哈，巴拉巴拉巴拉，喋喋以喋倚喋喋。
核心思路：
1.初始化：目标函数置为0，将物品按价值体积比的非增顺序排序
2.搜索：从根节点出发，尽量沿左孩子结点前进，当不能继续沿左孩子前进时，把搜索转到右子树，得到问题的一部分解。
3.估计：由部分解所能得到的最大价值：如果估计价值高于上界，继续向下搜索，直到找到可行解保存可行解，并用可行解得到的目标函数的值更新目标函数的上界，向上回溯，寻找其他可行解。若估计值小于目标函数的上界，则丢弃当前的部分解，向上回溯。
接下来解释一下接下来要出现的几个变量所代表的意思：
Weav：当前节点的估计价值
Wup：当前的最优值（注意，是当前，可能是最终的最优，也可能不是）
注意算法计算从这里就开始了！！！
第一步：
令Wup=0,将物体的序号按价值体积比，排序结果是（2， 1， 3， 4， 5）也就是此时的S和W需要按照新的物品顺序变一下，如下：
S=(5,15,25,27,30)
W=(12,30,44,46,50)
第二步：
生成节点1、 2、 3、 4、 5，（如下图所示）
得到部分解(1,1,1,0)，
（因为从节点5开始就不在是左孩子了，所以要在这里估计一下价值，来确定是否还继续往下搜索，估计价值时认为物品可以部分放入的）
估计当前部分解的价值为：Weva=（12+30+44） +（0） +（50-5-15-25） *（50/30） =94.3，
因为Weva>Wup
所以继续向下搜索生成结点6，
得到可行解(1,1,1,0,0),
得到价值为86，
第三步：
回溯：沿右孩子回溯到左孩子4（即节点4），生成相应右孩子7（即节点7）（如下图）
得到部分解(1,1,0,1)，
此时 估计价值Weva= （ 12+30） +（ 46） +（ 50-5-15-27）*（ 50/30） = 93 > Wup
因为Weva>Wup，
价值为88，
第四步：
回溯到8生成10，得到部分解(1,1,0,0), 估计部分解Weva=92>88
继续生成结点11，得到可行解(1,1,0,0,1), 更新Wup=92
第五步：
回溯，沿结点12向上回溯到结点3生成结点13，
得到部分解(1,0),此时Weva= （12） +（44）+（50-5-25） *（46/27） =90.1<92
向上继续回溯生成结点14，得到部分解(0),
此时得到的Weva=（0） +（30+44） +（50-15-25）*（46/27） = 91.03<92，
总结：
回溯法不愧称为深度优先算法，总是一条路先摸索完成后，再回过头去看看有没有更好的路走。与分支限界法正好相反。本人博客中也有分支限界法的介绍。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176788.html原文链接：https://javaforall.net
