Как организовать такое поведение?

Как можно было бы организовать такое поведение
имеется динамический массив c объектами вида
[
{"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 Мясо = цена (сумма всех позиций)
]

У каждой позиции имеется своя, персональная цена
Но если чел выбирает комплекс, у него срабатывает цена за комплекс и тогда персональная цена не имеет значения
например имеем два типа комплекса (комплексы формируются исходя из типа, например ['first', 'garnir', 'salad'])
Первое + Второе + Салат = МиниСет
Первое + Второе + Салат + Мясо = Стандарт

Нужно как то отфильтровать общий массив чтобы получить что то типа
[ // итого Борщ, Каша, Салат, Мясо 
{"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"},
]

Тотал сумм получается Комплекс1 + Комплекс2 + сумма блюд не вошедших в комплекс
Я думал как это сделать, но реализация получается слишком сложная
Создать объекты "матрицу" с ключами и при обновлении данных заполнять эти матрицы соответствующими типами а из исходного массива удалить значения, но это как-то сильно топорно, в лоб.
Может подскажете алгоритм, который помог бы изящно решить этот вопрос.
  • Вопрос задан
  • 256 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
У вас весьма услржненный вариант Set cover. Пишите полный перебор.

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

Если наборы не большие (скажем, не более четырех типов блюд) и всего блюд в заказе не много, то можно делать в тупую - перебирайте в функции все 2-3 блюда, кроме первого, двумя-тремя вложенными циклами. Потом берете типы этих блюд и смотрите, а есть ли у вас такой набор. Наборы можно хранить как список списков и искать там бинарным поиском или линейно. Или можно завести 4-х мерный массив и дополнить короткие наборы заглушкой вида "" до 4-х блюд. Такой ассоциативный набор для каждой комбинации типов блюд будет хранить есть ли такой набор и сколько он стоит.

Если же наборы могут быть больше или всего блюд многовато и надо бы побыстрее решать, то делайте следующее:
Для каждого типа блюд заведите список наборов, в которые такой тип входит.
В функцию передавайте блюда, сгруппированные по типам, и уже собранные наборы. Потом циклом перебирайте какой тип набора будете собирать с первым блюдом (у вас же есть список всех подходящих наборов) и вызывайте вторую рукурсивную функцию, которой передаются несобранные блюда, уже готовые наборы, какой тип набора собирается, и собранная часть текущего набора. Функция2 будет брать следующий неиспользованный тип в текущем наборе и, если блюда такого типа у вас есть, добавлять в цикле одно такое блюдо к набору и вызываться рекурсивно. Если весь набор собран, то рекурсивно вызывайте первую функцию.
В первой функции, помимо перебора всех наборов, после цикла, просто берите первое блюдо как само себя.

Когда первая функция получает пустой набор нераспределенных блюд, готовые наборы сравнивайте на оптимальность с глобальным ответом.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы