javascript整数数组中可用于获取总值的元素的最少数量

Question

有人可以帮忙吗？

如果我有总数或总和，例如 91

如何创建一个包含最少数量元素的数组来获得总值？

[50, 20, 10 , 5, 3, 2, 1] 总计这个数组将提供 91。

我知道如何使用 reduce 或类似的方法执行相反的功能:

<script>
var numbers = [65, 44, 12, 4];

function getSum(total, num) {
    return total + num;
}
function myFunction(item) {
    document.getElementById("demo").innerHTML = numbers.reduce(getSum);
}
</script>

Answer 1

贪心算法

这是一个使用贪心算法的解决方案。请注意，如果所有较小的数字都是所有较大数字的约数，例如 [50, 10, 5, 1]，此解决方案将正常工作。 (请参阅下面的动态算法，了解可以处理任何输入的解决方案)

50 mod 10 = 0
50 mod 5  = 0
50 mod 1  = 0
10 mod 5  = 0
10 mod 1  = 0
5  mod 1  = 0

const sum = xs => xs.reduce((acc, v) => acc + v, 0);

function pickSubset(options, total, currentPick) {

  if (sum(currentPick) === total) { return currentPick; }
  if (options.length === 0) { return null; }

  const firstVal = options[0];
  let res = null;

  if (sum(currentPick) + firstVal > total) {
    res = pickSubset(options.slice(1), total, currentPick);
  } else {
    let opt1 = pickSubset(options, total, currentPick.concat(options[0]));
    let opt2 = pickSubset(options.slice(1), total, currentPick.concat(options[0]));

    if (opt1 && opt2) {
      opt1.length < opt2.length ? res = opt1 : res = opt2
    } else if (opt1) {
      res = opt1;
    } else {
      res = opt2;
    }
  }

  return res;
}

const total = 73;
const options = [50, 25, 10, 5, 2, 1];

console.log(pickSubset(options, total, []));

要处理未排序的输入，您可以将其包装在另一个函数中并在将其传递给主函数之前对其进行排序。

const sum = xs => xs.reduce((acc, v) => acc + v, 0);

function pickSubset(options, total, currentPick) {

  const sortedOptions = options.sort((a, b) => b - a);

  function _pickSubset(options, total, currentPick) {

    if (sum(currentPick) === total) { return currentPick; }
    if (options.length === 0) { return null; }

    const firstVal = options[0];
    let res = null;

    if (sum(currentPick) + firstVal > total) {
      res = pickSubset(options.slice(1), total, currentPick);
    } else {
      let opt1 = pickSubset(options, total, currentPick.concat(options[0]));
      let opt2 = pickSubset(options.slice(1), total, currentPick.concat(options[0]));

      if (opt1 && opt2) {
        opt1.length < opt2.length ? res = opt1 : res = opt2
      } else if (opt1) {
        res = opt1;
      } else {
        res = opt2;
      }
    }

    return res;
  }

  return _pickSubset(sortedOptions, total, currentPick);
}



const total = 73;
const options = [50, 25, 10, 5, 2, 1].reverse();

console.log(pickSubset(options, total, []));

动态规划(自下而上的自然排序方法)

此解决方案适用于任何类型的输入。

function pickSubset(options, total) {

  function _pickSubset(options, change, minNums, numsUsed) {
    for (let i = 0; i < change + 1; i++) {
      let count = i;
      let newNum = 1;
      let arr = options.filter(v => v <= i);

      for (let j of arr) {
        if (minNums[i - j] + 1 < count) {
          count = minNums[i - j] + 1;
          newNum = j;
        }
      }

      minNums[i] = count;
      numsUsed[i] = newNum;
    }

    return minNums[change];
  }

  function printNums(numsUsed, change) {
    const res = [];
    let num = change;
    while (num > 0) {
      let thisNum = numsUsed[num];
      res.push(thisNum);
      num = num - thisNum;
    }
    return res;
  }

  const numsUsed = [];
  const numsCount = [];

  _pickSubset(options, total, numsCount, numsUsed);
  return printNums(numsUsed, total);
}

const options = [50, 10, 5, 2, 1];
console.log(pickSubset(options, 73));

动态编程(自上而下的内存方法)

// helper function that generates all the possible solutions
// meaning, all the possible ways in which we can pay the provided amount
// and caches those solutions;
// returns the number of possible solutions but that is not neccessary
// in this case
const _pickSubset = (toPay, options, currentPick, cache) => {
  if (toPay < 0) { return 0; }
  if (toPay === 0) {
    cache.add(currentPick);
    return 1;
  }
  if (options.length === 0) { return 0; }

  return _pickSubset(toPay - options[0], options, currentPick.concat(options[0]), cache)
    + _pickSubset(toPay, options.slice(1), currentPick, cache);
};

// memoize only with respect to the first two arguments - toPay, bills
// the other two are not necessary in this case
const memoizeFirstTwoArgs = fn => {
  const cache = new Map();
  return (...args) => {
    const key = JSON.stringify(args.slice(0, 2));
    if (cache.has(key)) { return cache.get(key); }
    const res = fn(...args);
    cache.set(key, res);
    return res;
  };
};

// uses memoized version of makeChange and provides cache to that function;
// after cache has been populated, by executing memoized version of makeChange,
// find the option with smallest length and return it
const pickSubset = (toPay, options) => {
  const cache = new Set();
  const memoizedPickSubset = memoizeFirstTwoArgs(_pickSubset);
  memoizedPickSubset(toPay, options, [], cache);

  let minLength = Infinity;
  let resValues;

  for (const value of cache) {
    if (value.length < minLength) {
      minLength = value.length;
      resValues = value;
    }
  }

  return resValues;
}

const options = [50, 25, 10, 5, 2, 1];
const toPay = 73;

console.log(pickSubset(toPay, options));