How to organize such behavior?

Question

JavaScript

How could such behavior be organized?
There is a dynamic array with objects of the form

[
{"dish_id":1,"title":"Борщ", "type":"first"},
{"dish_id":3,"title":"Салат","type":"salad"},
{"dish_id":2,"title":"Каша", "type":"garnir"},
{"dish_id":1,"title":"Борщ", "type":"first"},
{"dish_id":3,"title":"Салат","type":"salad"},
{"dish_id":2,"title":"Каша", "type":"garnir"},
{"dish_id":1,"title":"Борщ", "type":"first"},
{"dish_id":4,"title":"Мяско","type":"meet"},
// итого 3 Борща, 2 Каши, 2 Салата, 1 Мясо = цена (сумма всех позиций)
]

Each position has its own, personal price
But if a person chooses a complex, the price for the complex works for him and then the personal price does not matter,
for example, we have two types of complex (complexes are formed based on the type, for example ['first', 'garnir', ' salad'])

First + Second + Salad = MiniSet
First + Second + Salad + Meat = Standard

You need to somehow filter the total array to get something like

[ // итого Борщ, Каша, Салат, Мясо 
{"dish_id":1,"title":"Борщ", "type":"first"},
{"dish_id":2,"title":"Каша", "type":"garnir"},
{"dish_id":3,"title":"Салат","type":"salad"},
{"dish_id":4,"title":"Мяско","type":"meet"},
]
[ // итого Борщ, Каша, Салат 
{"dish_id":1,"title":"Борщ", "type":"first"},
{"dish_id":3,"title":"Салат","type":"salad"},
{"dish_id":2,"title":"Каша", "type":"garnir"},
]
[ // то что не вошло в комплекс
{"dish_id":1,"title":"Борщ", "type":"first"},
]

The total amount is Complex1 + Complex2 + the sum of the dishes not included in the complex I
thought how to do this, but the implementation is too complicated
something very clumsy, in the forehead.
Can you suggest an algorithm that would help to gracefully solve this issue.

Answer 1

You have a very useful Set cover option. Write full enumeration.
I can only give a couple of tips for implementation.
Write a recursive function which is passed the remaining unallocated dishes and a list of ready-made sets (sets from one dish are also sets). Try to adapt the first unallotted dish somewhere.
If the sets are not large (say, no more than four types of dishes) and there are not many dishes in the order, then you can do it stupidly - iterate through all 2-3 dishes in the function, except for the first one, in two or three nested loops. Then take the types of these dishes and see if you have such a set. Sets can be stored as a list of lists and searched there by binary search or linearly. Or you can create a 4-dimensional array and complete the short sets with a stub like "" up to 4 dishes. Such an associative set for each combination of types of dishes will store whether there is such a set and how much it costs.
If there can be more sets or there are too many dishes in total and it would be necessary to decide quickly, then do the following:
For each type of dish, make a list of sets in which this type is included.
Pass dishes grouped by types and already assembled sets to the function. Then loop through what type of set you will assemble with the first dish (you also have a list of all suitable sets) and call the second rucursive function, which is passed unassembled dishes, already prepared sets, what type of set is being built, and the assembled part of the current set. Function2 will take the next unused type in the current set and, if you have dishes of this type, add one such dish to the set in a loop and call it recursively. If the entire set is collected, then recursively call the first function.
In the first function, in addition to iterating over all sets, after the loop, just take the first dish as itself.
When the first function receives an empty set of unallocated dishes, compare the finished sets for optimality with the global answer.