1. def backtrack(w: [], v: [], W, i) -> int:
  2.     # base case
  4.     if i == len(w):
  5.         return 0
  7.     else:
  8.         if w[i] <= W:
  9.             # 在root处理问题
  10.             return max(
  11.                 v[i] + backtrack(w, v, W - w[i], i + 1),
  12.                 backtrack(w, v, W, i + 1))
  13.         else:
  14.             return backtrack(w, v, W, i + 1)
  17. def backtrack1(w: [], v: [], W, i, sum: int) -> int:
  18.     # base case
  20.     if i == len(w):
  21.         # 在树叶处理， 需要使用一个变量维护， 从树根到叶子迭代， 比较和其它叶子的值。
  22.         global maxsum
  23.         if maxsum< sum:
  24.             maxsum = sum
  25.         return
  27.     else:
  28.         if w[i] <= W:
  29.             # 在root处理问题
  30.             backtrack1(w, v, W - w[i], i + 1, sum + v[i]),
  31.         # 任何情况都可以选
  32.         backtrack1(w, v, W, i + 1, sum)
  35. if __name__ == '__main__':
  36.     W = 4
  37.     w = [2, 1, 3]
  38.     v = [4, 2, 3]
  39.     print(backtrack(w, v, W, 0))
  40.     maxsum = 0
  41.     print(backtrack1(w, v, W, 0, 0), maxsum)
  44. # bp算法在顶层处理问题的解， 或者在底层处理

总结

  • 回溯是自顶向下的过程， 是一颗树的遍历过程
  • 问题的解可以在root处理， 也可以在叶子处理
    • 问题存在多解时候， 在叶子处理
    • 问题只有一个解时， 在root处理，减少不必要的参数传递