Ответ в теме: Задача о ранце на Prolog

      Комментарии к записи Ответ в теме: Задача о ранце на Prolog отключены
#2205

Исходные предметы опишем во внутренней базе данных:

%% item(name, weight, cost)
item(ball, 0.5, 10).
item(belcher, 0.2, 11).
item(hat, 0.1, 20).
item(glass, 0.5, 5).
item(book, 0.5, 13).
item(bread, 0.5, 7).
item(wurst, 0.2, 15).

Во время поиска решение (набор предметов и их стоимость) можно накапливать также во внутренней БД. Предикат, в котором будет сохраняться результат должен быть объявлен динамическим — это позволит обновлять значение можно с помощью встроенных Предикаты assert и retract:

%% bag(Items, Cost)
:- dynamic
  bag/2. 

Правило bagpack_problem:

  1. удаляет информацию обо всех предыдущих решениях;
  2. инициализирует начальное значение результата пустым мешком с нулевой ценностью предметов;
  3. выполняет перебор всех решений (при помощи встроенного предиката fail);
  4. выбирает накопленный результат из базы данных.

bagpack_problem(BagWeight, Bag, Cost):-
  rem_all_bags, 
  assert(bag([], 0)),
  select_items(BagWeight, [], 0), fail;
  bag(Bag, Cost), !.

Для удаления информации о предыдущих решениях необходимо удалить все факты bag/2 из БД, для этого выполняется retract до тех пор, пока это возможно. Если retract выполнить не удалось, значит все факты удалены, т.е. работа функции завершена:

rem_all_bags:-
  retract(bag(_Items, _Cost)), rem_all_bags; !.

Правило перебора решения:

  1. в противном случае обрабатывает одно из возможных решений (но на этом поиск не завершается);
  2. пытается поместить еще один предмет в мешок, остальные обработать рекурсивно;
  3. если в мешок нельзя поместить ни одного предмета — правило завершает работу.

select_items(_BagWeight, CurrentBag, CurrentBagCost):-
  bag(Items, Cost),
  Cost < CurrentBagCost,
  retract(bag(Items, Cost)),
  assert(bag(CurrentBag, CurrentBagCost)),
  write(CurrentBag), nl.
select_items(BagWeight, CurrentBag, CurrentBagCost):-
  item(ItemName, ItemWeight, ItemCost),
  ItemWeight =< BagWeight,
  \+ member(ItemName, CurrentBag),
  BagWithItemWeight is BagWeight - ItemWeight,
  BagWithItemCost is CurrentBagCost + ItemCost,
  select_items(BagWithItemWeight, [ItemName|CurrentBag], BagWithItemCost).

При обработке возможного решения выполняется сравнение стоимости предметов в нем с предыдущим лучшим решением (хранящимся в базе данных). Если новое решение лучше старого — выполняется обновление информации в базе данных. Для просмотра обработанных вариантов и наглядной демонстрации работы программы все найденные варианты выводятся на экран (на алгоритм это не влияет).

При добавлении нового предмета в мешок нужно выбрать из базы такой предмет, вес которого не превышает вместимость мешка. Кроме того, необходимо проверить, что предмет не был ранее помещен в мешок — используется встроенный предикат member (оператор \+ для таких диалектов, как Turbo Prolog или Visual Prolog должен быть замене на предикат NOT).