I am trying to solve the knapsack problem in prolog. Following is my implementation.

```
% 'ks' is compound term which has 4 argumets                                                                                                                                                                                                   
%   1 - List of items to be chosen from.                                                                                                                                                                                                       
%   2 - Maximum weight a knapsack can carry.                                                                                                                                                                                                   
%   3 - Selected items which sum of weights is less than or equal to knapsack capacity.                                                                                                                                                            
%   4 - The gain after choosing the selected item.                                                                                                                                                                                             

% base conditions where input list contains only one items and                                                                                                                                                                                 
% it is either selected or excluded.                                                                                                                                                                                                           
ks([item(W1, V1)], W, [item(W1, V1)], V1):- W1 =< W.
ks([item(W1, _)], W, [], 0):- W1 > W.

% An item from the input list is chosen in the knapsack.                                                                                                                                                                                       
% In that case, we recurse with smaller list with reduced weight constraint.                                                                                                                                                                  
ks(ItemList, MaxWeight, SelectItems, Gain) :-
    append(Prefix, [item(W1, V1)|Suffix], ItemList),
    append(Prefix, Suffix, RemList),
    NewWeight is MaxWeight - W1,
    W1 =< MaxWeight,
    append([item(W1, V1)], SelectItems1, SelectItems),
    ks(RemList, NewWeight, SelectItems1, Gain1),
    Gain is V1 + Gain1.

% An item from the input list is not chosen in the knapsack.                                                                                                                                                                                   
% In that case, we recurse with smaller list but with the same weight constraint.                                                                                                                                                             
ks(ItemList, MaxWeight, SelectItems, Gain) :-
    append([P1|Prefix], [item(W1, V1)|Suffix], ItemList),
    append([P1|Prefix], Suffix, RemList),
    not(member(item(W1, V1), SelectItems)),
        ks(RemList, MaxWeight, SelectItems, Gain).

```

The input to the program will be list of items as below. in term **item(W, V)** W is weight of the item while V is value of the item. Goal to maximize the value for the given weight constraint.

```
ks([item(2,3), item(3,4), item(4,5), item(5,8), item(9,10)], 20, List, Gain).
List = [item(2, 3), item(3, 4), item(4, 5), item(5, 8)],
Gain = 20 ;

```

While I am able to generate all the combinations of items with above program, I am not able to code to find out the maximum gain only.

Could any one please point me the right direction?

Thanks.