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));
}