Algorithm for multi-dimensional maximisation

Question

I would like to devise an algorithm that given:

1. An array of dishes with macronutrient information (proteins, fats and carbohydrates, in grams), constrained to a maximum of around 200 items.
2. A desired macro-nutrient target (proteins, fats, carbohydrates, in grams)

would output the same list of dishes, ordered by the best-fit maximising all macronutrients (with the same "importance") for each macro. For example:

let dishes = [
  { proteins: 10, fats: 5, carbohydrates: 10 },
  { proteins: 15, fats: 10, carbohydrates: 5 },
  { proteins: 0, fats: 5, carbohydrates: 20 }
]

let target = { proteins: 30, fats: 20, carbohydrates: 20 }

let result = process(dishes, target)

print(result)

Would output (something like):

[
  [{ proteins: 10, fats: 5, carbohydrates: 10 }, { proteins: 15, fats: 10, carbohydrates: 5 }],
  [{ proteins: 15, fats: 10, carbohydrates: 5 }, { proteins: 0, fats: 5, carbohydrates: 20 }],
  [{ proteins: 10, fats: 5, carbohydrates: 10 }, { proteins: 0, fats: 5, carbohydrates: 20 }],
  [{ proteins: 15, fats: 10, carbohydrates: 5 }]
]

I've been doing a bit of reading around, and initially I thought that perhaps some sort of multidimensional knapsack algorithm might be a good fit for this problem. What I'd like is either confirmation of my initial findings (that a m-knapsack is a good fit) or any other insight around algorithms that better fit this particular situation. If there is a well-known implementation of the algorithm in JavaScript, that would be great, too.

Answer 1

"Knapsack" is not an algorithm, it is a class of problems, so knowing if your problem falls into this category does not give you an algorithm.

So yes, your problem is actually a special case of a Knapsack problem, it is a "Subset Sum" problem (and yes, it is a multi dimensional variant).

At least the single-dimensional topic has been subject of extensive research over decades, and hence there are virtually dozens of algorithmic approaches. Unfortunately, there is no "standard algorithm" for this. Finding an exact solution is actually NP complete, even in the single dimensional case, but if you are just looking for "good" solutions, there are polynomial time approximation algorithms.

I would recommend to implement something like Simulated Annealing or Tabu Search, but don't expect to find an algorithm which will deliver you always the "best" solutions within a reasonable amount of time.