如何编写计算无重复名称路径最大概率、无需逐数组写嵌套循环的JS函数

暴力穷举实现（递归回溯法） #

不需要手动写多层嵌套循环，用回溯递归的方式自动适配任意长度的子数组层级，核心思路是逐层处理子数组，每一层遍历可选的对象，跳过重复的name，递归到最后一层时更新最大乘积即可，代码实现如下：

function getMaxProbability(data) {
  let maxProduct = 0
  // 递归参数：当前处理的子数组下标、已使用的name集合、当前累计的概率乘积
  function backtrack(index, usedNames, currentProduct) {
    // 所有子数组处理完成，更新最大乘积
    if (index === data.length) {
      maxProduct = Math.max(maxProduct, currentProduct)
      return
    }
    // 遍历当前子数组的所有可选对象
    for (const obj of data[index]) {
      // 跳过已经选过的name
      if (usedNames.has(obj.name)) continue
      // 选中当前对象，进入下一层递归
      usedNames.add(obj.name)
      backtrack(index + 1, usedNames, currentProduct * obj.probability)
      // 回溯撤销选择，尝试当前层的下一个对象
      usedNames.delete(obj.name)
    }
  }
  backtrack(0, new Set(), 1)
  return maxProduct
}

// 测试示例数据集
const testData = [
  [{name: 'AAA', probability: .7}, {name:'BBB', probability: .6}, {name: 'CCC', probability: .1}],
  [{name: 'AAA', probability: .8}, {name: 'CCC', probability: .7}, {name: 'DDD', probability: .4}],
  [{name: 'AAA', probability: .8}, {name: 'BBB', probability: .5}, {name: 'DDD', probability: .8}]
]
console.log(getMaxProbability(testData)) // 输出结果为0.392

优化方案参考 #

• 剪枝优化：由于所有概率都是不大于1的正数，因此只要当前累计的乘积已经小于等于当前记录的最大乘积，后续层级的选择只会让乘积更小，直接终止当前分支的递归即可，只需要在backtrack函数开头添加代码if (currentProduct <= maxProduct) return就能大幅减少无效计算。
• 动态规划优化：如果数据集规模较大（子数组数量多、每个子数组元素多），可以用二进制掩码作为状态标识，dp[mask]表示选中mask对应二进制位标记的name时的最大乘积，逐层更新DP表即可，时间复杂度比暴力递归低很多。

内容的提问来源于stack exchange，提问作者user11631308