Пролог - Как найти максимальный набор элементов, что их сумма равна N

Question

моя игра о выборе максимального набора элементов из заданного списка, что их сумма равна N

пример: L=[1,1,2,2,3,2,4,5,6], N = 6, Sub Список будет равен [1,1,2,2]

Мне нужна подсказка с использованием программирования логики ограничений.

Answer 1

В SWI-Prolog имеется библиотека для программирования с ограничениями логики. Это называется clpfd.

:-use_module(library(clpfd)). 

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

... 
    length(List, M), 
    L in 0..M, 
    labeling([max(L)],[L]), 
... 

Далее L можно использовать для построения списка L переменных, которые соответствуют индексам элементов из List. Поскольку эти индексы должны быть в порядке возрастания, chain/2 может использоваться для создания ограничений #</2 между любыми двумя последовательными индексами.

... 
    length(Indices, L), 
    Indices ins 1..M, 
    chain(Indices, #<), 
... 

Используя эти индексы, список с элементами из List может быть построен. nth1/3 полезен здесь, но с небольшим трюком.

... 
nth1a(List, N, E):- 
    nth1(N, List, E). 
... 
    maplist(nth1a(List), Indices, SubSequence), 
... 

И сумма этого списка должен быть N:

... 
    sum(SubSequence, #=, N) 
... 

Как только требуется длинная последовательность, once/1 может быть использован для остановки после первого найдено решение.

Некоторые примеры запросов:

?- longest_subsequence([1,1,4,4,6], 9, S). 
S = [1, 4, 4]. 

?- longest_subsequence([1,1,4,4,6], 11, S). 
S = [1, 4, 6]. 

?- longest_subsequence([1,1,4,4,6], 21, S). 
false. 

---

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

Answer 2

В ответ мы используем clpfd и немного lambda:

:- use_module([library(clpfd), 
       library(lambda)]). 

На основе meta-predicatemaplist/4 и ограничений (ins)/2 и sum/3 мы определяем:

zs_selection_len_sum(Zs, Bs, L, S) :- 
    same_length(Zs, Bs), 
    Bs ins 0..1, 
    maplist(\Z^B^X^(X #= Z*B), Zs, Bs, Xs), 
    sum(Bs, #=, L), 
    sum(Xs, #=, S). 

Примеры запросов с использованием labeling/2 с опцией max/1:

 
?- zs_selection_len_sum([1,1,4,4,6],Bs,L,8), labeling([max(L)],Bs). 
    Bs = [1,1,0,0,1], L = 3 
; Bs = [0,0,1,1,0], L = 2 
; false. 

?- zs_selection_len_sum([1,1,3,4,5],Bs,L,7), labeling([max(L)],Bs). 
    Bs = [1,1,0,0,1], L = 3 
; Bs = [0,0,1,1,0], L = 2 
; false. 

?- zs_selection_len_sum([1,1,2,2,3,2,4,5,6],Bs,L,6), labeling([max(L)],Bs). 
    Bs = [1,1,0,1,0,1,0,0,0], L = 4 
; Bs = [1,1,1,0,0,1,0,0,0], L = 4 
; Bs = [1,1,1,1,0,0,0,0,0], L = 4 
; Bs = [0,0,1,1,0,1,0,0,0], L = 3 
; Bs = [0,1,0,0,1,1,0,0,0], L = 3 
; Bs = [0,1,0,1,1,0,0,0,0], L = 3 
; Bs = [0,1,1,0,1,0,0,0,0], L = 3 
; Bs = [1,0,0,0,1,1,0,0,0], L = 3 
; Bs = [1,0,0,1,1,0,0,0,0], L = 3 
; Bs = [1,0,1,0,1,0,0,0,0], L = 3 
; Bs = [1,1,0,0,0,0,1,0,0], L = 3 
; Bs = [0,0,0,0,0,1,1,0,0], L = 2 
; Bs = [0,0,0,1,0,0,1,0,0], L = 2 
; Bs = [0,0,1,0,0,0,1,0,0], L = 2 
; Bs = [0,1,0,0,0,0,0,1,0], L = 2 
; Bs = [1,0,0,0,0,0,0,1,0], L = 2 
; Bs = [0,0,0,0,0,0,0,0,1], L = 1 
; false.