如何计算所有可能的值组合以涵盖动态金额？

Question

我试图返回所有可能的“管道”组合，以至少覆盖所提供的脚数。

此问题类似于常见的硬币更改算法。

管道的增量为10'，25'和50'。

我看过here和here的例子似乎很接近，但是，我想要归还所有可能的组合而不是简单地计算它们。

这是我目前的代码：

 let allCombos = [];
  let pipeAmounts = [50, 25, 10];

  function findPiping (feet, index, combo) {
    if (index > pipeAmounts-1) {
      return;
    }
    let makeCombos = (amountOfFeet, index, combo) => {
      let currentPipe = pipeAmounts[index];
      let newFeet = amountOfFeet - currentPipe;

      combo.push(currentPipe);

      if (newFeet >= currentPipe) {
        makeCombos(newFeet, index, combo);
      }

      if (newFeet < currentPipe && newFeet > 0) {
        makeCombos(newFeet, index, combo);

      }
      if (newFeet < 0) {
        allCombos.push(combo);
        combo = [];
        makeCombos(feet, index+1, combo);
      }
    };
    makeCombos(feet, index, combo);
  }
  findPiping(60, 0, []);
  console.log('allCombos', allCombos)

目前我的代码只生成2种组合。

如何找到涵盖所需足部量的所有可能组合？

Answer 1

这是一个递归，它返回所有有效组合，至少涵盖了所需的feet，给出了amounts中无限选择的增量。

function f(feet, amounts, i, combo){
  if (feet <= 0 || i == amounts.length)
    return [combo];
  
  if (i == amounts.length - 1){
    while (feet > 0){
      combo.push(amounts[i]);
      feet -= amounts[i];
    }
    return [combo];
  }

  let combos = f(feet, amounts, i+1, combo.slice());

  while (feet > 0){
    combo.push(amounts[i]);

    feet -= amounts[i];

    combos = combos.concat(
      f(feet, amounts, i+1, combo.slice())
    );
  }
  
  return combos;
}

let pipes = [50, 25, 10];

console.log(JSON.stringify(f(60, pipes, 0, [])));