# 回溯算法

  • 回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径
  • 回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”

为了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段

每个阶段,我们都会面对一个岔路口,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走

# 回溯思想

  • 回溯算法非常适合用递归代码实现,或者使用栈来模拟
  • 剪枝操作是提高回溯效率的一种技巧。利用剪枝,我们并不需要穷举搜索所有的情况,从而提高搜索效率

# 0-1背包问题

我们有一个背包,背包总的承载重量是 Wkg。现在我们有 n 个物品,每个物品的重量不等,并且不可分割。我们现在期望选择几件物品,装载到背包中。在不超过背包所能装载重量的前提下,如何让背包中物品的总重量最大?

回溯算法

const pack = [23, 12, 5, 2, 9]
function maxWeight(pack, weight, sum = 0, n = 0) {
  if (sum == weight || n >= pack.length) {  // 出口条件
    return sum
  }
  let max1 = 0, max2 = 0
  max1 = maxWeight(pack, weight, sum, n + 1)  // 不装
  if (sum + pack[n] <= weight) {  // 装
    max2 = maxWeight(pack, weight, sum + pack[n], n + 1)
  }
  return Math.max(max1, max2) // 返回不超过weight的最大值
}
console.log(maxWeight(pack, 45))
1
2
3
4
5
6
7
8
9
10
11
12
13
上次更新: 2020-8-18 22:14:00