首页 > Web开发 > 详细

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

时间:2021-09-11 10:06:11      阅读:7      评论:0      收藏:0      [点我收藏+]

例如:有一组数字,[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],需要从这一组数字中寻找最优的数字组合,让数字组合的总和最接近但不超过这个某个值,比如14,且组合的数字数量尽量多。

> [4, 10]有2个数字,可构成等于14,最接近14的数字组合。

> [1, 2, 3, 4]有4个数字,可构成等于10,较接近14的数字组合。

以上2个组合,第2个组合才是更优,是否还有更优的数字组合呢?

 

通过以下封装的方法即可求出是否还有更优的数字组合,使用如下:

// 示例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));
}

 

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

原文:https://www.cnblogs.com/jardeng/p/15250200.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!