通过仅从起点减去允许的数字来尽可能接近零的算法-解网

问：

假设我们有一个任意整数，位置等于1850

我们还有一个整数数组，等于[150, 200, 500]

我们可以通过以下方式达到零：

减去三倍（500*3），等于350components[2]position
减去，使其为 150components[1]position
减去，使其为 0components[0]position

因此，我使用组件数组中的整数，从中减去，直到剩下尽可能少的（0）position

编码示例：

var components = [500, 750, 1000];
var position = 2250;

position -= components[1]; // goal is now 1500
position -= components[0] * 3; // goal is now 0

可视化

问题：有没有一种算法可以通过仅减去允许的数字来确定从数字中达到零的最佳方法？

该算法最好使用尽可能少的分量/减法。

我尝试了一些幼稚的方法，例如暴力破解，但这并不理想，因为性能在我的应用程序中非常重要。

JavaScript 算法数学优化时间复杂度

根据的值，您可以大幅减少搜索空间。500*2 = 1000 ->我们总是可以将 500 的 2 次使用量减少 1000 中的一次。此外，2*750=1500=3*500 ->我们总是可以用 3*500 替换 750 的两种用法。或 4*750 x 3*1000。我们也知道，我们需要至少使用一次 750 才能得到 2250，因为没有其他组件可以产生 50。...components

0赞 Rishabh Dhawad 10/12/2023

您可以将此问题作为动态编程任务来处理。目标是找到要从位置减去的最小分量（来自组件数组的整数），使其变为零或尽可能接近零。

0赞 MrSmith42 10/12/2023

您可以使用回溯。首先尽可能多地减去最大的分量，当您无法达到 0 时，回溯并尝试其他分量。

答：

0赞 Nina Scholz 10/12/2023 #1

您可以回溯并使用有序数组首先获得最大值。

function getSum(array, sum) {
    function iter(index, temp, left) {
        if (!left) return temp;
        if (left < 0 || index >= array.length) return;
        return iter(index, [...temp, array[index]], left - array[index])
            || iter(index + 1, temp, left);
    }

    return iter(0, [], sum);
}

console.log(getSum([1000, 750, 500], 2250));

function getCombinations(array, rest) {
  function test(state, col) {
    let best = state;
    const value = array[col];

    // what's the most I can subtract with this value?
    const max = Math.floor(state.rest / value);
    // if this is the last column to check (0), subtracting 4*value, 3*, 2*, ...
    // will not yield a better result that subtracting 5*value
    // so check only the max value.
    const min = col ? 0 : max;

    for (let i = max; i >= min; --i) {
      const tmp = i ? {
        ...state,
        [value]: i,
        rest: state.rest - value * i
      } : state;
      
      const item = col ? test(tmp, col - 1) : tmp;

      // no need to check any further
      if (item.rest === 0) return item;

      if (item.rest < best.rest) best = item;
    }

    // log checked state; since this function is recursive, 
    // avoid logging the same `best` for each `col`
    col || console.log("checked", best);

    return best;
  }

  // copy and sort ASC
  array = [...array].sort((a, b) => a - b);

  const state = { rest };
  array.forEach(value => state[value] = 0); // optional

  // going from right to left (hi to lo) so that I don't have to 
  // check `col < array.length-1` all the time. 
  // this way I can check for `col !== 0` or simply `col?`
  return test(state, array.length - 1);
}

// get 3 random values
const set = new Set();
while (set.size < 3) set.add(Math.floor(Math.random() * 999 + 1));

console.log("values", ...set);

console.log(getCombinations(set, 2250));

从技术上讲，这是一种暴力算法，尝试组合，但有一些短路。就像避免一些无意义的组合，并在找到余数为0的组合时提前返回。

它从最高值到最低值向后工作，尝试尽可能减少余数，然后检查是否有更好的结果，该值的计数较低，以确保当有多个可能的结果时，它首先找到计数最低的结果。

上一个：根据距离生成具有给定平均乘积的数字的算法

下一个：Python 2D 路径规划算法 - 动态窗口方法，机器人在达到目标之前失速

通过仅从起点减去允许的数字来尽可能接近零的算法

Algorithm to get as close to zero as possible by subtracting only allowed numbers from a starting point

评论

评论