NP-полный рюкзак - PullRequest
Новая
       28

NP-полный рюкзак

9 голосов
/ 06 июня 2011

Я видел это ECLiPSe решение проблемы, упомянутой в этом XKCD комиксе. Я пытался преобразовать это в чистый Пролог. 

go:-
    Total = 1505,
    Prices = [215, 275, 335, 355, 420, 580],
    length(Prices, N),
    length(Amounts, N),
    totalCost(Prices, Amounts, 0, Total),
    writeln(Total).

totalCost([], [], TotalSoFar, TotalSoFar).
totalCost([P|Prices], [A|Amounts], TotalSoFar, EndTotal):-
    between(0, 10, A),
    Cost is P*A,
    TotalSoFar1 is TotalSoFar + Cost,
    totalCost(Prices, Amounts, TotalSoFar1, EndTotal).

Я не думаю, что это лучшее / наиболее декларативное решение, которое можно придумать. У кого-нибудь есть предложения по улучшению? Заранее спасибо!

Ответы [ 2 ]

6 голосов
/ 07 июня 2011

Так как вы упомянули SWI-Prolog, почему бы не 

?- use_module(library(clpfd)).

и library(lambda)

?- Total = 1505, Prices = [215, 275, 335, 355, 420, 580],
   maplist(\P^A^M^(P*A #= M, A #>=0),Prices,Amounts,Ms), sum(Ms, #=, Total).

Указав это, все переменные в списке Amounts находятся в ограниченном диапазоне.Таким образом, нет необходимости «делать математику» для верхней границы (которая часто все равно идет не так).Чтобы увидеть конкретные решения, необходима маркировка / 2: 

?- Total = 1505, Prices = [215, 275, 335, 355, 420, 580],
   maplist(\P^A^M^(P*A #= M, A #>=0),Prices,Amounts,Ms), sum(Ms, #=, Total),
   labeling([], Amounts).
    Total = 1505,
    Prices = [215,275,335,355,420,580],
    Amounts = [1,0,0,2,0,1],
    Ms = [215,0,0,710,0,580] ;
    Total = 1505,
    Prices = [215,275,335,355,420,580],
    Amounts = [7,0,0,0,0,0],
    Ms = [1505,0,0,0,0,0].
5 голосов
/ 06 июня 2011

Ваш подход генерации и тестирования должен быть понятен любому программисту Prolog с опытом работы более нескольких дней.Вот некоторые незначительные изменения: 

go(Amounts) :-
    Prices = [580, 420, 355, 335, 275, 215],
    totalCost(Prices, Amounts, 0, 1505),
    write(Amounts), nl.

totalCost([], [], Total, Total).
totalCost([P|Prices], [A|Amounts], SoFar, Total):-
    Upper is (Total-SoFar)//P,
    between(0,Upper,A),
    SoNear is SoFar + P*A,
    totalCost(Prices, Amounts, SoNear, Total).

Я изменил go / 0 на go / 1 , так что движок Prolog откатится назад и выдаст все решения (тамдва).Вызовы length / 2 могут быть опущены, потому что totalCost / 4 выполняет работу по построению списка Amounts равной длины с ценами.Я использовал write / 1 и nl / 0 , чтобы сделать его немного более портативным.

In totalCost / 4 Я сократил некоторые изимена переменных / аргументов и немного шутливое имя для аргумента аккумулятора.Способ, которым я наложил проверку, что наш аккумулятор не превышает желаемого значения Total, использует ваш исходный вызов между / 3 , но с вычисленной верхней границей вместо константы.На моей машине это сократило время работы с минут до секунд.

Добавлено: Я должен упомянуть здесь, что было сказано в моем комментарии выше, что пункты меню теперь упорядочены от самых дорогих донаименее.Использование предиката SWI-Prolog time / 1 показывает, что это сокращает объем работы с 1923 до 1070 выводов.Основное улучшение (в скорости) достигается за счет использования вычисленных границ для A, а не диапазона от 0 до 10 для каждого элемента. 

time((go(A),false)).

Обратите внимание на дополнительные скобки вокруг составной цели, так как в противном случае SWI-Prolog считает, что мывызов неопределенного предиката time / 2 .

...