Алгоритм распределения

Программирование
#1

Всем привет. Снова туплю над вроде бы не сложной задачей. Думала, пока буду писать вопрос, как обычно, придет мысля. Но мысля, увы, не пришла, так что публикую.

Кароч, задача такая. Собрались десять друзей отмечать новый год. Каждый принес с собой по блюду на праздничный стол. В каждом блюде всего три порции. И друзья договорились, что каждый попробует по одной порции от трех блюд. Свое, естественно, никто есть не хочет. У каждого из друзей есть свои предпочтения и свои антипатии(их может быть неограниченное количество, а может не быть вовсе). Задача в том, чтобы предоставить каждому три наиболее подходящих ему блюда.

Я предполагаю, что нужно выразить свои предпочтения в числовой форме. Например, изначально любое блюдо имеет для меня ценность 0. Я прохожусь по его ингредиентам и проставляю +10 над каждым любимым и -10 над каждым нелюбимым. Потом складываю эти числа, и получится что-то вроде оценки.

Но это как-то слишком просто. Например, получится, что оценка салата, где есть курица (которую я люблю) и спаржа (которую я не люблю) будет равняться нулю. Также как и любого салата, в котором нет ни одного моего любимого ингредиента. Что с этим делать?

Дальше, к примеру, курицы нет нигде. Но есть так называемые “группы ингредиентов”. Можно глянуть группу “мясо” и вместо курицы выбрать индейку (таким бы “одногруппникам” я вместо +10 ставила бы +5). Но опять же, я не совсем понимаю, когда лучше производить эти расчеты: сразу или после анализа любимых/нелюбимых ингредиентов, когда получилась нехватка подходящих блюд.

А как потом это все распределить? То есть “блюдо 1” может быть одинаково высоко оценено пятью людьми. Как среди них выбрать тех троих, кому оно достанется?

В общем, в голове каша, крутится что-то несформулированное и в алгоритм не вырисовывается. Может, кто сталкивался с подобными задачами? Если не трудно, растолкуйте человеческим языком. Ну или хотя бы пните, по каким запросом в гугле искать. Стопудово же есть какой-нибудь метод решения таких задач.

#2

А она откуда? Если с собеседований и т.п., то может красивого решения и нету, а просто чтоб посмотреть как над таким будет думать кандидат )

Может быть тут что-то типа задачи о рюкзаке (там как-то дерево перебирать если предметов не очень много), получить наибольшую сумму ценностей.
Задача о рюкзаке — Википедия

#3

Из головы) Решила немного синтаксис шарпа вспомнить, давно не практиковалась, ну и чтоб не просто так команды тыцать, такую программку написать. На самом деле суть ее немного другая, с блюдами я пример привела, чтоб понятней было. Да в принципе там и красивого решения особо не нужно, нужно хоть какое-то)

Да, рюкзак я смотрела. Чет не въезжаю я в него. Точнее, в моей задаче получается не один рюкзак, а много. И как приспособить решение одного рюкзака на многие, так, чтоб “владельцам рюкзаков” не было обидно, что в первый рюкзак влезли самые ценные вещи, а в другой - самые ценные из оставшихся, и так далее, - не соображу.

#4

Блюда оценивать не по шкале баллов а в процентном соотношении. Если блюдо предпочтительно больше чем трем гурманам исходить из общего веса блюда и уменшать вес порций.
Как бы так.

#5

Что имеется в виду под процентным соотношением? Типа, процентное соотношение ингредиента относительно блюда? Если да, то не катит. Вес в расчет не берем. Порции не уменьшаем.

Я привела пример в блюдах для простоты, но с таким же успехом это может быть распределение товара по магазинам, распределение ресурсов на карте в игре-стратегии типа цивилизации, рассаживание гостей за столом и т.д. Поэтому цифры только целые) Если рядом с Петей мест всего два, а хотят рядом с ним сидеть пять барышень, нельзя же разрезать Петю)

З.Ы. Самое обидное, что я то ли по похожей задаче курсач в колледже писала, то ли она рядом с моей в методичке валялась. Зато хоть вспомнила, как предмет назывался) Методы оптимизации. Ща буду его курить. Но вопрос все равно не снят, так что если у кого-то вдруг появятся идеи, буду рада послушать.

#6

У Вас две сложности: недоопределенность задачи и неопределенность алгоритма.
Люблю такое)
Можно начинать с приведения входных данных.
В системе с оценками предельное максимальное их количество - оценка каждой тройки блюд каждым участником, любую можно свести к этому, форма оценки - отдельный вопрос. Задача: выбрать 10 троек из полученного множества. Критерии открыты, например, средний максимум и минимальный разброс или максимум минимального.

Если же переформулировать условие “Свое, естественно, никто есть не хочет”, на “каждый готов или не готов поменяться с кем-то”, то получается задача даже с простыми эвристическими алгоритмами неухудшающего обмена при изначальном состоянии “каждый ест свое”. Здесь можно даже ограничиться матрицами готовности обмена блюд (даже одной, если только для своего на чужое) и матрицами сочетаемости блюд (можно также одной общей). Критерием может быть просто максимальное разнообразие. Это про сокращенное количество входных данных. Возможно будет в бытовом плане проще приниматься людьми объяснением случайности обмена. Т.е. можно не пытаться построить абс. максимум, а сыграть в случай. Хотя решать можно и разными продвинутыми алгоритмами и оценками тоже можно расширить.