js实现凑数
实现凑数算法的 JavaScript 方法
问题描述
凑数问题通常指从给定数组中找出若干元素，使它们的和等于或接近目标值。以下是几种常见的实现方式：
递归回溯法
适用于元素较少的情况，通过递归尝试所有可能的组合：
function findSubsetSum(nums, target) {
const result = [];
const backtrack = (start, path, sum) => {
if (sum === target) result.push([...path]);
for (let i = start; i < nums.length; i++) {
if (sum + nums[i] > target) continue; // 剪枝
path.push(nums[i]);
backtrack(i + 1, path, sum + nums[i]);
path.pop();
}
};
backtrack(0, [], 0);
return result;
}
// 示例
const nums = [2, 4, 6, 8];
console.log(findSubsetSum(nums, 10)); // 输出 [[2,8], [4,6]]动态规划法
适用于较大数据集，通过构建 DP 表记录可能达到的和：
function subsetSumDP(nums, target) {
const dp = Array(target + 1).fill(false);
dp[0] = true;
for (const num of nums) {
for (let i = target; i >= num; i--) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[target];
}
// 示例
console.log(subsetSumDP([3, 5, 7], 10)); // 输出 true近似凑数算法
当需要最接近目标值时，可使用贪心或动态规划优化：
function closestSum(nums, target) {
let closest = Infinity;
nums.sort((a, b) => a - b);
const dfs = (index, currentSum) => {
if (Math.abs(currentSum - target) < Math.abs(closest - target)) {
closest = currentSum;
}
for (let i = index; i < nums.length; i++) {
if (currentSum + nums[i] > target) break; // 提前终止
dfs(i + 1, currentSum + nums[i]);
}
};
dfs(0, 0);
return closest;
}
// 示例
console.log(closestSum([1, 2, 3, 4], 9)); // 输出 10性能优化建议
- 排序剪枝：先对数组排序，可在递归中提前终止无效分支。
- 记忆化：使用缓存避免重复计算（如斐波那契数列中的优化）。
- 限制深度：对大规模数据设置递归深度限制或改用迭代。
实际应用场景
- 财务预算分配
- 游戏道具组合优化
- 资源调度中的任务分配
以上方法可根据具体需求选择，递归法直观但性能有限，动态规划适合精确解，近似算法适用于模糊匹配场景。
