从数字输入计算最佳拟合

Question

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

问题:
我有许多不同类型的碗（5-15种）。每个类型的碗都可以容纳最少和最多的食物量（每人）。以五个碗为例：

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

规则如下:

• 每个碗总是填满食物，直到最小或最大值。
• 尽可能避免浪费或赠送免费食物。

我的目标:
输入人数，并且函数计算出我需要哪些碗来最佳搭配。

例如，我说我有12个人。在这种情况下，只需要一个D碗。

但如果我输入36个人，则预计最佳搭配如下：
1 X E: 可容纳20人
1 X C: 可容纳10人
1 X B: 可容纳6人

这总共可以容纳36个人。如果您知道更好或更有效的方法，请告诉我。

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

由于我是初学者，请尽量详细解释。

- Ali Lotfi

---

这更像是一个数学问题而不是编程问题。你有一个数学解决方案吗？那么只需要将其翻译成JS即可。但是，如果你没有一个，这可能不是最好的论坛来询问：那么数学stackexchange怎么样？ - Terry

@Terry 说得好。我会尝试用数学方法解决，然后再用JS看看它的效果。 - Ali Lotfi

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>

- Yanick Rochon