What is this task type?

Question

There are people and the food they prefer:
John -20> Apple
John -10> Pear
Ethan -20> Apple
Ethan -5> Orange
Michael -10> Pear
Michael -10> Limon

The numbers indicate how strongly they prefer the respective food.
i.e. John likes Apple more than Pear (20 > 10). And so for everyone.

The task is to distribute food to absolutely all people, trying to give the most preferred food as much as possible.

Expected result:
John -10> Pear
Ethan -20> Apple
Michael -10> Limon
S = 10 + 20 + 10 = 40

But if so:
John -20> Apple
Ethan -5> Orange
Michael -10> Pear
S = 20 + 5 + 10 = 35 (<40 — not expected result)

With different initial data, there may be several solutions with the same maximum S.
These solutions must be kept without discarding.

(1) What kind of task is this and (2) What algorithm should be applied?

Answer 1

1. Assignment problem.
2. Hungarian algorithm.

Python code:

# pip install munkres

from typing import Dict, Union

from munkres import Munkres

G = {
    'John': {'Apple': 20, 'Pear': 10},
    'Ethan': {'Apple': 20, 'Orange': 5},
    'Michael': {'Pear': 10, 'Limon': 10},
}


def find_matching(graph: Dict[str, Dict[str, Union[int, float]]],
                  matching_type=Union['max', 'min'],
                  return_type=Union['list', 'int', 'float', 'number'],
                  big_number: int = 1_000_000):
    negate = -1 if matching_type == 'min' else +1
    items_d, rows_d, cols_d = dict(), dict(), dict()
    n, m = 0, 0
    for row_name, cols in graph.items():
        if row_name not in rows_d:
            rows_d[n] = row_name
            rows_d[row_name] = n
            n += 1
        for item_name, cost in cols.items():
            if item_name not in cols_d:
                cols_d[m] = item_name
                cols_d[item_name] = m
                m += 1
            items_d[(rows_d[row_name], cols_d[item_name])] = cost * negate
    matrix = [[items_d[(i, j)] if (i, j) in items_d else big_number for j in range(m)] for i in range(n)]
    indexes = Munkres().compute(matrix)
    r_list = []
    r_number = 0
    for i, j in indexes:
        cost = matrix[i][j] * negate
        r_list.append(((rows_d[i], cols_d[j]), cost))
        r_number += cost
    if return_type == 'int':
        return int(r_number)
    if return_type == 'float':
        return float(r_number)
    if return_type == 'number':
        return r_number
    return r_list


print(find_matching(graph=G, matching_type='max', return_type='number'))
print(find_matching(graph=G, matching_type='max', return_type='list'))