求助一个算法，求最接近目标值的组合？

Question

题目描述

求助一个算法：给定一个浮点数数组和一个目标值，在数组中找出最接近目标值的浮点数组合；
例如：数组[1.2, 1.5, 2.1, 3.5, 4.2]，目标值：7.6，则结果为[1.2, 2.1, 4.2]

Answer 1

回溯+剪枝

const combinationClosest = (arr, target) => {
  let res = [], cur = [], minD = target
  const n = arr.length
  const dfs = (i, d) => {
    if (d >= minD) return // 如果都是正数，加上这行代码剪枝，否则去掉
    if (i == arr.length) {
      const abs = Math.abs(d)
      if (abs < minD) {
        minD = abs
        res = [...cur]
      }
      return
    }
    const a = arr[i++]
    cur.push(a)
    dfs(i, d + a)
    cur.pop()
    dfs(i, d)
  }
  dfs(0, -target)
  return res
}

console.log(combinationClosest([1.2, 1.5, 2.1, 3.5, 4.2], 7.6))
// [1.2, 2.1, 4.2]

时间复杂度：\( O(2^n) \)
空间复杂度：\( O(n) \)

Answer 2

暴力，子数组。

<?php

$nums = [1.2, 1.5, 2.1, 3.5, 4.2];
$target = 7.6;

$arr = [];
$cha = PHP_INT_MAX;

$result = [[]];
foreach ($nums as $num) {
    foreach ($result as $item) {
        $newItem = array_merge($item, [$num]);
        if ($cha > $newCha = abs(array_sum($newItem) - $target)) {
            $cha = $newCha;
            $arr = $newItem;
        }
        $result[] = $newItem;
    }
}

var_dump(
    array_sum($arr)
    , $arr
);