js/ts 获取通过子项数字组合能组合成的最优组合

// 示例1，目标值14
this.getOptimalGroup(14, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
// 更优组合，[5, 2, 3, 4] 总和： 14

// 示例2，目标值26，数字可以无序排列
this.getOptimalGroup(26, [1.5, 16, 1.6, 220, 190, 48, 8, 20, 25, 140, , 14, 3])
// 最优组合，[1.5, 1.6, 14, 8] 总和： 25.1

/**
 * 获取通过子项数字组合能组合成的最优组合
 * @param target 目标数字
 * @param arr 子项数字数组
 */
private getOptimalGroup(target: number, arr: Array<number>) {
  // 将子项数字数组从小到大排序
  arr.sort((a, b) => a - b)

  // 理论最优数字组合
  let theoryOptimalArr: Array<number> = [],
    // 理论最接近目标的数字
    theoryOptimalTarget = 0,
    // 目标数字副本
    targetCopy = target

  //#region 计算理论最优
  console.group(‘计算理论最优‘)
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i]
    if (num > targetCopy) break

    // 消耗数字
    targetCopy -= num
    // 加入到理论最优数字组合
    theoryOptimalArr.push(num)
  }
  // 计算理论最优目标数字
  theoryOptimalTarget = theoryOptimalArr.reduce((total, item) => total += item, 0)
  console.log(‘%c理论最接近目标的数字：‘, ‘color: orange;‘, theoryOptimalTarget)
  console.log(‘%c理论最优数字组合：‘, ‘color: orange;‘, theoryOptimalArr)
  console.groupEnd()
  //#endregion

  //#region 寻找更优组合
  console.group(‘寻找更优组合‘)
  // 当前最优目标数字，默认初始等于理论最优目标数字
  let currOptimalTarget = theoryOptimalTarget,
    // 理论最优数字组合数组副本
    theoryOptimalArrCopy = [...theoryOptimalArr],
    // 当前最优数字组合
    currOptimalArr: Array<number> = [],
    // 当前数字组合累计值
    currTotal = 0,
    // 是否匹配
    match = false
  const otherNums = arr.filter(x => !theoryOptimalArr.includes(x) && x < target)
  otherNums.length && console.log(‘%c可供用于替换的数字(按从小到大的顺序排列)：‘, ‘color: gray;‘, otherNums)
  for (let i = 0; i < theoryOptimalArr.length; i++) {
    // 重置理论最优数字组合数组副本为原始值，重新开始下一轮替换
    theoryOptimalArrCopy = [...theoryOptimalArr]
    console.group(`[第 ${i + 1} 轮替换] 替换理论最优数字组合数组的第 ${i + 1} 个数字：`, theoryOptimalArr[i])
    for (let j = 0; j < otherNums.length; j++) {
      const replaceNum = otherNums[j]
      theoryOptimalArrCopy[i] = replaceNum
      currTotal = theoryOptimalArrCopy.reduce((total, item) => total += item, 0)
      match = currTotal > theoryOptimalTarget && currTotal <= target && currTotal > currOptimalTarget
      if (!match) {
        console.log(`%c当前数字 ${replaceNum} 替换数字 ${theoryOptimalArr[i]} 后总和 ${currTotal} 超出目标数字 ${target}，后续其他数字 [${otherNums.filter(x => x > replaceNum).join(‘, ‘)}] 不再继续替换`, ‘color: red;‘)
        break
      }

      currOptimalTarget = currTotal
      currOptimalArr = [...theoryOptimalArrCopy]
      console.log(`%c当前数字 ${replaceNum} 替换数字 ${theoryOptimalArr[i]} 后总和 ${currTotal} 未超出目标数字 ${target}，可组合成更优、更接近目标数字的组合：`, ‘color: blue;‘, currOptimalArr, ‘总和：‘, currOptimalTarget)
    }
    console.groupEnd()
  }

  console.log(‘\n‘)
  if (currOptimalArr.length) {
    console.log(‘%c最优的数字组合：‘, ‘color: green;‘, `${currOptimalArr.map(x => `${x}`).join(‘ + ‘)} = ${currOptimalArr.reduce((total, item) => total += item, 0)}`)
  } else {
    console.log(‘%c没有更优的数字组合，理论最优数字组合可作为最优‘, ‘color: red;‘, `${theoryOptimalArr.map(x => `${x}`).join(‘ + ‘)} = ${theoryOptimalArr.reduce((total, item) => total += item, 0)}`)
  }
  console.log(‘%c最接近目标的数字：‘, ‘color: green;‘, `${currOptimalTarget}元`)
  console.groupEnd()
  //#endregion
}

/**
 * 获取通过子项数字组合能组合成的最优组合
 * @param total 目标数字
 * @param arr 子项数字数组
 */
private GetOptimalGroup(total: number, arr: Array<number>) {
  arr.sort((a, b) => { return a - b });
  let sum = 0;
  //原始数组
  let first = [];
  let firstsum = 0
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
    if (sum > total) break;
    first.push(arr[i]);
    firstsum += arr[i];
  }
  console.log(‘原始最大个数：‘ + first.length + ‘,最大和：‘ + firstsum + ‘,组合:‘ + JSON.stringify(first));
  //可以替换的所有数字
  let canchange = [];
  for (let i = 0; i < arr.length; i++) {
    const arr_item = arr[i];
    for (let j = 0; j < first.length; j++) {
      const first_item = first[j];
      if (arr_item > first[0] && first.lastIndexOf(arr_item) < 0 && arr_item - first_item < (total - firstsum) && arr_item - first_item > 0) {
        canchange.push(arr_item);
        break;
      }
    }
  }
  console.log(‘可替换数字：‘ + JSON.stringify(canchange));

  let tmpsum = firstsum;
  let rightpair = [];
  //和最大的新组合
  let newArr = [];
  //逐个替换
  for (let i = 0; i < first.length; i++) {
    const first_item = first[i];
    for (let j = 0; j < canchange.length; j++) {
      const canchange_item = canchange[j];
      if (firstsum + canchange_item - first_item > tmpsum && firstsum + canchange_item - first_item < total) {
        tmpsum = firstsum + canchange_item - first_item;
        newArr = first.concat();
        newArr[i] = canchange_item;
        console.log(‘【有效替换】【‘ + canchange_item + ‘】替换【‘ + first_item + ‘】;最大个数：‘ + newArr.length + ‘,最大和：‘ + tmpsum + ‘,组合:‘ + JSON.stringify(newArr));
        rightpair = [newArr];

      } else if (firstsum + canchange_item - first_item == tmpsum) { //另外答案
        newArr = first.concat();
        newArr[i] = canchange_item;
        console.log(‘【有效替换】【‘ + canchange_item + ‘】替换【‘ + first_item + ‘】;最大个数：‘ + newArr.length + ‘,最大和：‘ + tmpsum + ‘,组合:‘ + JSON.stringify(newArr));
        rightpair.push(newArr)
      } else {
        console.log(‘【无效替换】【‘ + canchange_item + ‘】替换【‘ + first_item + ‘】;最大和：‘ + (firstsum + canchange_item - first_item));
      }
    }
  }
  console.log(‘最终最大个数：‘ + newArr.length + ‘,最大和：‘ + tmpsum + ‘,组合:‘ + JSON.stringify(rightpair));
}