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

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

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

Алгоритм упаковки рюкзака должен:

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

bagpack_problem(BagWeight, Bag, Cost):-
  init_bag,
  
  findall(item(ItemName, ItemWeight, ItemCost), item(ItemName, ItemWeight, ItemCost), Items),
  all_length_compromise(Items, [], Compromise),
  try_bag(Compromise, BagWeight), fail; 

  bag(Bag, Cost), !.

Инициализация рюкзака удаляет всю старую информацию о нем и добавляет запись о пустом рюкзаке с нулевой стоимостью вещей:

init_bag:-
  retract(bag(_Items, _Cost)), init_bag, !; 
  assert(bag([], 0)), !.

При попытке упаковки набора вещей необходимо проверить его соответствие размеру рюкзака. Если стоимость такого набора выше чем у вещей, упакованных в рюкзак в настоящее время – старая запись о рюкзаке удаляется, на ее место записывается текущий набор:

try_bag(Bag, BagWeightLimit):-
  bag_weight_cost(Bag, BagWeight, BagCost),
  BagWeightLimit >= BagWeight, 
  bag(CurrentBag, CurrentBagCost),
  BagCost > CurrentBagCost,
  retract(bag(CurrentBag, CurrentBagCost)),
  assert(bag(Bag, BagCost)).

Вспомогательное правило bag_weight_cost примает на вход набор вещей, определяет его цену и вес:

bag_weight_cost([], 0, 0):-!.
bag_weight_cost([item(_ItemName, ItemWeight, ItemCost)|Tail], Weight, Cost):-
  bag_weight_cost(Tail, TailWeight, TailCost),
  Weight is TailWeight + ItemWeight,
  Cost is TailCost + ItemCost.

Цена и вес пустого рюкзака равны нулю. Из непустого рюкзака выбирается первая вещь, вытаскивается, а остальные обрабатываются рекурсивно. К полученному результату добавляется цена и вес вытащенного предмета.