JavaScript递归实现查找总长度不超过2280的最大货品发货位置组合方案

核心实现逻辑 #

你需要筛选的是极大满足条件的子集，判断规则为：

• 组合总长度 < 2280
• 无法再加入任何一个未被包含在组合中的货品，加入后总长度仍小于2280

代码优化说明 #

首先修正原有代码中两个问题：

1. 测试数据中货品长度字段名大小写不统一，建议先统一为TotalProductLength避免取值错误
2. 原有k_combinations中长度判断逻辑错误，改为生成所有组合后统一筛选

完整实现代码 #

const totalTruckLengthAvailable = 2280
// 测试数据统一字段名
const arr = [
  {"shipLOC": "ALASTE", "TotalProductLength": 480},
  {"shipLOC": "BRONHT", "TotalProductLength": 1520},
  {"shipLOC": "ZIHNER", "TotalProductLength": 120},
  {"shipLOC": "MEADON", "TotalProductLength": 700},
  {"shipLOC": "RUSPOW", "TotalProductLength": 200}
]

// 生成k个元素的组合
function k_combinations(set, k) {
  let i, j, combs, head, tailcombs
  if (k > set.length || k <= 0) return []
  if (k == set.length) return [set]
  if (k == 1) {
    combs = []
    for (i = 0; i < set.length; i++) {
      combs.push([set[i]])
    }
    return combs
  }
  combs = []
  for (i = 0; i < set.length - k + 1; i++) {
    head = set.slice(i, i + 1)
    tailcombs = k_combinations(set.slice(i + 1), k - 1)
    for (j = 0; j < tailcombs.length; j++) {
      combs.push(head.concat(tailcombs[j]))
    }
  }
  return combs
}

// 生成所有非空组合
function combinations(set) {
  let k, i, combs = [], k_combs
  for (k = 1; k <= set.length; k++) {
    k_combs = k_combinations(set, k)
    for (i = 0; i < k_combs.length; i++) {
      combs.push(k_combs[i])
    }
  }
  return combs
}

// 计算组合总长度
function calcTotalLength(comb) {
  return comb.reduce((sum, item) => sum + item.TotalProductLength, 0)
}

// 筛选符合要求的最优组合
function filterOptimalCombinations(allCombs, allItems, maxLength) {
  // 第一步：筛选所有总长度符合要求的组合
  const validCombs = allCombs.filter(comb => calcTotalLength(comb) < maxLength)
  // 第二步：筛选极大组合，无法再加任何其他元素
  return validCombs.filter(comb => {
    const currentTotal = calcTotalLength(comb)
    // 提取所有不在当前组合里的元素
    const restItems = allItems.filter(item => !comb.includes(item))
    // 只要有一个元素加进去仍符合长度要求，就不是最优组合
    for (let item of restItems) {
      if (currentTotal + item.TotalProductLength < maxLength) {
        return false
      }
    }
    return true
  })
}

// 执行逻辑
const allCombs = combinations(arr)
const optimalCombs = filterOptimalCombinations(allCombs, arr, totalTruckLengthAvailable)
// 输出每个组合的shipLOC
const result = optimalCombs.map(comb => comb.map(item => item.shipLOC))
console.log(result)

运行结果 #

上述测试数据运行后输出的最优组合为：

[
  ["ALASTE", "BRONHT", "ZIHNER"],
  ["BRONHT", "MEADON"],
  ["ALASTE", "ZIHNER", "MEADON", "RUSPOW"]
]

三个组合的总长度分别为2120、2220、1500，均无法再加入其他货品仍满足长度要求。

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