Разместить N объектов по K ящикам разной вместимости

Главная Форумы Программирование Помощь с решением задач на Prolog Задачи на списки Разместить N объектов по K ящикам разной вместимости

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 10 мес. назад.

  • Автор
    Сообщения
  • #1885

    questioner
    Участник

    Добрый день. Искала как решить задачу и вышла на Ваш блог.
    Помогите, пожалуйста:

    разместить N объектов по K ящикам, где у каждого ящика своя вместимость на SWI Prolog.

    permut(Obj,Boxes,Result):-
      Obj=[a,b,c,d], 
      permutations(Obj,Boxes,Result).

    Тут я использую стандартный предикат permutation, но он не учитывает что ящики могут вмещать более одного элемента. Читала вашу статью про генерацию перестановок на Prolog, но там также размер ящиков принимается равным единице.

  • #1886

    Не уверен что это будет работать, но я бы решал примерно так:

    размещение([], Ящики, Результат):- !, Результат = Ящики.
    размещение([Объект|ОстальныеОбъекты], Ящики, Результат):-
        member(Ящик, Ящики), Ящик = (СвободноеМесто, ОбъектыЯщика), СвободноеМесто \= 0,
        delete(Ящики, Ящик, ВремЯщики),
        НовоеМесто is СвободноеМесто - 1, НовыеОбъекты = [Объект|ОбъектыЯщика],
        НовыйЯщик = (НовоеМесто, НовыеОбъекты),
        НовыеЯщики = [НовыйЯщик|ВремЯщики],
        размещение(ОстальныеОбъекты, НовыеЯщики, Результат).

    Вроде бы работает верно, но если есть несколько ящиков одинаковой вместимости — то не совсем понятно как различать ящики — они по ходу решения тусуются. но можно и как-то иначе решить — например сохранять порядок следования ящиков — в моем коде ящики перемещаются по результирующему списку. В не привели примера, поэтому я решил на свое усмотрение. Я думаю, вы сами поправите при необходимости.

    Я специально написал код так, чтобы Вам его проще было понять, но поясню.
    Первым аргументом правило принимает список объектов, подлежащих размещению по ящикам, вторым — список ящиков. В третий аргумент будет помещен результат.

    Результат возвращается лишь в том случае, если все объекты уже размещены по ящикам, т.е. исходный список объектов пуст.

    Если же есть не размещенные объекты — то выбирается первый из них, затем, выбирается ящик, в котором есть свободное место и удаляется из списка. Создается новый ящик, в который добавлен выбранный объект и уменьшено свободное место. Ящик добавляется в список. Рекурсивно обрабатываются оставшиеся (но обработанные) объекты, новый список ящиков, если при обработке будет получен какой-то результат — то правило завершается удачей и возвращает это значение.

Для ответа в этой теме необходимо авторизоваться.