回溯算法定义：在搜索中寻找问题的解，如果发现不满足条件，返回上一步，尝试另一条路径
回溯应用：深度优先探索、八皇后、0-1背包、全排列等
以0-1背包问题为例，有背包。 背包的总载重量是Wkg。 现在我们有n件物品。 每件物品的重量不同，不可分割。 我们现在愿意挑选一些物品装在背包里。 如何使背包中物品的总重量达到最大，不超过背包可以承载的重量？
private int maxw=integer.min _ value； //结果为maxW加上private int [ ] weight={ 2，2，4，6，3 }； //物品重量private int n=5； //项目数private int w=9； //背包承受的最大重量publicvoidf(intI，int cw )/f ) 0，0 ) if ) CW==w|||I==n )/CW==w表示装满，i==n表示所有物品(f ) I1，cw；//选择不放入第I个物品if (cw weight[i] ) f ) I1，CW weight [ I ] )；//选择第I项}}回溯算法最适合使用递归实现。 代码实现很简单，但往往有重复计算。 计算过程如下图所示。
您可以使用“记忆化”或“笔记”方法进行优化，如以下代码所示：
private int maxw=integer.min _ value； //结果为maxW加上private int [ ] weight={ 2，2，4，6，3 }； //物品重量private int n=5； //项目数private int w=9； //背包承受的最大重量private boolean [ ] [ ] mem=new boolean [5] [ 10 ]； //注，默认值falsepublicvoidf(intI，int cw )/f ) 0，0 ) if ) CW==w||I==n )/CW==w )=w表示已满(if ) mem[I][CW] )返回； //重复状态mem[i][cw]=true； //记录(I，cw )此状态f ) I1，cw )；//选择不放入第I个物品if (cw weight[i] ) f ) I1，CW weight [ I ] )；//选择放入第I个项目}}其效率基本上与动态计划相同，代码比动态计划更容易理解。