我目前正在嘗試找出計算最佳擬合的演算法。
問題是什么：
我有很多型別的碗（5-15 種）。每種型別的食物都有最小數量和最大數量（每人）。舉個例子，我有五個碗：
答：可容納 3 到 5 人的食物。
B：可容納 4 至 6 人份的食物。
C：可容納 5 到 10 人的食物。
D：容納 10 到 15 人的食物。
E：容納 15 到 20 人的食物。
規則是：
- 一個碗總是裝滿食物，直到最小量或最大量。
- 盡可能避免贈送免費食物或浪費食物。
我想做的是：
提供一定數量的人，然后函式計算出最適合我需要的碗數量。
舉個例子，我會說我有 12 個人。在這種情況下，D 碗是最好的，因為只需要一個碗。
但如果我讓出 36 個人。我希望我會得到最好的 fitis：
1 XE：最多可容納 20 人
1 XC：最多可容納 10 人
1 XB：最多可容納 6 人
總共有36人。如果您知道更好或更有效的方法，請告訴我。
如何在 Javascript 中創建這樣的函式？
由于我是小學生，請盡量解釋清楚。
uj5u.com熱心網友回復：
這個問題是一個優化問題。以下代碼遍歷所有可能的解決方案，并使用一些啟發式（或確定性函式）以最低成本計算解決方案。可能還有更多優化的空間，但你的問題空間相對較小。
// 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>轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/514784.html