-1
Предположим, у меня есть магазин & продавать товары только в двух группах.Как решить (или назвать) этот ранцеподобный алгоритм
- Если я продам карандаш и ластик, я зарабатываю $ 3
- Если я продаю КАРАНДАШ и мрамор, я зарабатываю $ 2
- Если я продам линейку и ластик, я зарабатываю $ 2
Каждый покупатель желает купить до 1 позиции каждого & Я хочу получать максимальную прибыль. Поэтому продажа № 1 и № 2 является незаконной, потому что это будет 2 карандаша. № 1 И № 3 также является незаконным из-за ластиков. Итак, юридические шаги: только # 1, только # 2, только # 3, или # 2 И # 3. Поскольку последний вариант имеет прибыль в 5 долларов, я должен это сделать.
Как бы решить эту проблему за полиномиальное время? Если это np-hard, то какой эвристический подход может приблизиться ко мне? Если ничего другого, имеет ли эта проблема имя?
Что вы пробовали? Мы готовы помочь с вашей домашней работой, но вам нужно показать усилие :) – Parker
Моя единственная мысль - это вложенный цикл (для каждой группы, которая включает карандаш, для каждой группы, которая включает в себя линейку ....), но это быстро растет. Не стоит беспокоиться об обмане меня от учебы, это на самом деле то, что я строю на вершине венгерского алгома для проблемы маршрутизации транспортных средств. –
Каковы ограничения? Похоже, он должен всегда продавать 2 и 3 каждому клиенту, я не могу полностью понять этот вопрос. – Parker