javascript - 从数字输入计算最佳拟合

Question

我目前正在尝试找出计算最佳拟合的算法。

问题是什么:
我有很多类型的碗(5-15 种)。每种类型都拥有最小量和最大量的食物(每人)。例如，我有五个碗:

A:可容纳 3 到 5 人的食物。
B:可容纳 4 到 6 人的食物。
C:容纳 5 到 10 人的食物。
D:容纳 10 到 15 人的食物。
E:容纳 15 到 20 人的食物。

规则是:

• 碗里总是装满食物，直到达到最小量或最大量为止。
• 尽可能避免赠送免费食物或产生浪费。

我想做什么:
提供一定数量的人，然后函数计算出最适合我需要的碗的数量。

举个例子，我会说我有 12 个人。在这种情况下，碗 D 是最好的，因为只需要一个碗。

但如果我让出36个人。我希望我能得到最好的 fitis:
1 X E:最多可容纳 20 人
1 X C:最多可容纳 10 人
1 X B:最多可容纳 6 人

总共有 36 人。如果您知道更好或更有效的方法，请告诉我。

如何在 Javascript 中创建这样的函数？

由于我是小三，请尽量解释清楚。

Answer 1

这道题是一道优化题。以下代码遍历所有可能的解决方案，并使用一些启发式(或确定性函数)来计算成本最低的解决方案。可能还有更多优化空间，但你的问题空间相对较小。

// 1. List of bowl 
const bowlTypes = [
  {
    name: "A",
    description: "holds between 3 and 5 persons worth of food",
    min: 3,
    max: 5
  },
  {
    name: "B",
    description: "holds between 4 to 6 persons worth of food",
    min: 4,
    max: 6
  },
  {
    name: "C",
    description: "holds between 5 and 10 persons worth of food",
    min: 5,
    max: 10
  },
  {
    name: "D",
    description: "holds between 10 and 15 persons worth of food",
    min: 10,
    max: 15
  },
  {
    name: "E",
    description: "holds between 15 and 20 persons worth of food",
    min: 15,
    max: 20
  }
];

// 2. Create a cost function for the best combination of bowls
//    e.g. may use sum of the bowls' costs
function getCost(bowls, surplus) {
  const total = bowls.reduce((total, { min, max }) => total + ((max - min) / 2), 0);

  // penalty for more bowls, heavy penalty for surplus
  // adjust function to calibrate, perhaps add actual
  // bowl cost to data set      
  return bowls.length + total + (surplus * surplus);
}


// 3. Evaluate how many bowls we need given a number of persons
function evaluatePersons(persons) {
  const bowlCount = bowlTypes.length;
  let bestSolution;
  
  // recursive function walking all possible options.
  const findSolution = (bowls, servings, startIndex) => {
    // while we can add more bowls...
    if (servings > 0) {
      // try next combination
      for (let bowlIndex = startIndex; bowlIndex < bowlCount; ++bowlIndex) {
        const bowl = bowlTypes[bowlIndex];
        findSolution([ ...bowls, bowl ], servings - bowl.max, bowlIndex);
      }
    // if the current solution has enough, or too many servings
    } else {
      // get amount of surplus
      const surprlus = Math.abs(servings);
      // get the cost of this solution
      const cost = getCost(bowls, surprlus);
      
      // if the current solution is better than any previous one
      if (!bestSolution || (cost < bestSolution.cost)) {
        bestSolution = { bowls, cost, surprlus };
      }
    }
  };
  
  // init first step
  for (let bowlIndex = 0; bowlIndex < bowlCount; ++bowlIndex) {
    findSolution([], persons, bowlIndex);
  }
  
  // optimize solution
  bestSolution.bowls = Array.from(bestSolution.bowls.reduce((map, bowl) => {
    if (map.has(bowl.name)) {
      map.get(bowl.name).qty = map.get(bowl.name).qty + 1;
    } else {
      map.set(bowl.name, { ...bowl, qty:1 });
    }
  
    return map;
  }, new Map()).values());

  // return our best solution
  return bestSolution;
}


// UI for testing purposes
const inputPersons = document.getElementById('inputPersons');
const output = document.getElementById('output');

inputPersons.addEventListener('change', () => {
  const solution = evaluatePersons(inputPersons.value);
  
  const verbatim = solution.bowls.map(bowl => `${bowl.qty} x ${bowl.name}: ${bowl.description}`).join('\n');
  const debugString = JSON.stringify(solution, null, 3);

  output.innerHTML = verbatim + '\n--------\n' + debugString;
});

main {
  width: 100%;
  display: flex;
  flex-direction: column;
}

form {
  flex: 0;
}

pre {
  min-height: 200px;
  flex: 1;
  border: 1px solid black;
  background-color: #e7e7e7;
  padding: 10px;
}

<main>
  <form>
    <input type="number" id="inputPersons" />
  </form>

  <pre><code id="output"></code></pre>
</main>