[SOLVED] Knapsack Find Max

Knapsack Find Max

I am studying prolog in a course, I have an exercise to implement the knapsack problem. I succeeded in writing the code, but I cant figure out how to find the max profit out of all the possible solutions.

Here's the code

between( Lo, Hi, Nu ) :-
   (  integer( Lo ),
      integer( Hi ),
      integer( Nu )
   -> Nu >= Lo,
      Nu =< Hi
   ;  integer( Lo ),
      integer( Hi ),
      var( Nu )
   -> repeat( Lo, Hi, Nu )
   ).


add_list(A, [], [A]).
add_list(A, L, [A|L]).
add_list([], L, L).
add_list([H|T], L, L1) :- add(H, L2, L1), add_list(T, L, L2).


knapsack_go(L, Limit, Amounts, Profit):-
    knapsack(L, Limit, Amounts, 0, Profit).
knapsack([], _, _, ProfitSoFar, ProfitSoFar).
knapsack([Item-Size-Value| Tail], Limit, Amounts, ProfitSoFar, Profit):-
    Upper is Limit//Size,
    between(0, Upper, A),
    Profit2 is (A * Value) + ProfitSoFar,
    Limit2 is Limit - (A*Size),
    add_list(A, Amounts2, Amounts), 
    knapsack(Tail, Limit2, Amounts2, Profit2, Profit).

How can I do max on the profit?

EDIT: here is how i run it:

knapsack_go([a-7-9, b-11-14, c-19-24], 100, Amounts, Profit).

I think I'm asking how do I make prolog generate all solutions, because right now I get a solution and I can press on space to get the next one. So how do I generate all solutions, keep them in a list or something and pick the best profit.

Some more info - L is a list of Item-Size-Value, Limit is the remaining space in the bag, Amounts is a list of Item1 amount, Item2 amount and so on

Solution

You could use :

findall(Profit-Amounts,knapsack_go([a-7-9, b-11-14, c-19-24], 100, Amounts, Profit),L).

This will collect all the solutions in list L ,where L will be a list of the form [Profit-Amounts|T].

Now, to find the max profit you could write:

  max([First | Rest], Result) :- First =FirstP-_
  maxC(Rest, First,FirstP, Result).

  maxC([], Sofar, _, Sofar).

  maxC([First | Rest], _, Max, Result) :-
  First = FirstP-_
  Max =< FirstP,
  maxC(Rest, First, FirstP,Result).

  maxC([First | Rest], Sofar,Max,Result):-
  First = FirstP-_
  Max > FirstP,
  maxC(Rest, Sofar, Max, Result).

This will return the max of the profits if you want the Amounts list you would use above FirstP-Amounts where now is FirstP-_ in the predicates max,maxC.