Calculate best fit from number input-CodePudding

I'm currently trying to figure out the algorithm to calculate the best fit.

What is the problem:
I have many types of bowls (5-15 types). Each type holds a minimum amount and a maximum amount of food (per person). So as an example I have five bowls:

A: holds between 3 and 5 persons worth of food.
B: holds between 4 to 6 persons worth of food.
C: holds between 5 and 10 persons worth of food.
D: holds between 10 and 15 persons worth of food.
E: holds between 15 and 20 persons worth of food.

The rules are:

A bowl is always filled up with food until the minimum amount or the maximum amount.
Prevent giving away free food or having waste as much as possible.

What I want to do:
give in an amount of people, and that the functions calculates what is the best fit of the amount of bowls that I need.

So as an example I would say that I have 12 people. In this case Bowl D is the best since only one bowl is needed.

But if I give in 36 people. I would expect that I would get that the best fitis:
1 X E: Holds up to 20 people
1 X C: Holds up to 10 people
1 X B: Holds up to 6 people

That makes a total of 36 people. If you know a better or more efficient way let me know.

How to create such a function in Javascript?

Since I'm a junior, please try to explain as much as possible.

CodePudding user response：

This question is an optimization problem. The following code walk every possible solutions and use some heuristics (or deterministic function) to calculate the solution with least cost. There may be room for more optimizations, but your problem space is relatively small.

// 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 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>