以下是近期遇到的三个计(算)算(法)题... 提到这些问题的时候简单理了下思路，后面又以JavaScript代码实现并顺便记个笔记...
至于是什么场景下遇到这些题的么... ：)
问题一：从无序数组里取出M个值，总和为N，得出一个解即可
给出思路：
1. 递归直到长度为M为止，得出数组子集；
2. 对得出的数组子集进行计算，如果相加的和等于N(如果设置容差T，则相加的和与N的差距小于容差T)，则将子集数据存入combArr；
2.1. 默认只取第一个值，取到后跳出循环；
2.2. 如果设置取所有结果，则继续循环求之后的子集。
代码如下：
const arr = [14, 30, 38, 15, 34, 20, 10, 5, 35, 32, 27, 11, 9, 50, 21, 29, 3, 47, 26, 39, 18, 17, 40, 37, 49, 23, 22, 43, 33, 1, 24, 8, 16, 12, 25, 28, 48, 2, 41, 44, 45, 46, 4, 13, 42, 36, 31, 19, 6, 7]; // 参数 数组 数量 总和 容差 是否取全部结果function getCombination(array, count, sum, tolerance, allResult) { const combArr = []; const $tolerance = isNaN(tolerance) ? 0 : tolerance; if (!count || isNaN(count)) {; return combArr.push([]), combArr; } // 是否取所有结果 let getAllResult = false; const generateIdxComb = ($originArray, $count, $array) => { if ($count === 0) { const $sum = $originArray.reduce((a, b) => a + b); if (Math.abs(sum - $sum) <= $tolerance) { combArr.push($originArray); if (allResult) { getAllResult = true; } } return; } for (let i = 0, len = $array.length; i <= len - $count; i++) { if (combArr.length && !getAllResult) { break; } generateIdxComb($originArray.concat($array[i]), $count - 1, $array.slice(i + 1)); } } // 递归取子集 (generateIdxComb)([], count, array); return combArr; } getCombination(arr, 3, 21); // output [[14, 5, 2]]getCombination(arr, 3, 21, 0, true); // output [[14, 5, 2],[14, 3, 4],...] 27个组合
问题一的扩展，背包问题：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高
在上面的代码做判断条件的修改：
const arr = '[{weight: 1,price: 15}, {weight: 3,price: 12}, {weight: 5,price: 16}, {weight: 6,price: 9}, {weight: 7,price: 18}, {weight: 9,price: 11}]'; // 数组 数量 限定值function getMaxComb(array, count, sum) { let combArr = []; let totalPrice = 0; if (!count || isNaN(count)) {; return combArr; } const generateIdxComb = ($originArray, $count, $array) => { if ($count === 0) { const $sumWeight = $originArray.reduce((a, b) => a + b.weight, 0); if ($sumWeight <= sum) { const $totalPrice = $originArray.reduce((a, b) => a + b.price, 0); if ($totalPrice > totalPrice) { totalPrice = $totalPrice; combArr = $originArray; } }; return; } for (let i = 0, len = $array.length; i <= len - $count; i++) { generateIdxComb($originArray.concat($array[i]), $count - 1, $array.slice(i + 1)); } } // 递归取子集 (generateIdxComb)([], count, array); return
