Knapsack Find Max

Question

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

If your implementation gives you _all_ solutions, in no specific order, you can always just collect them all, then pick out the maximum. For examples, see [here](http://stackoverflow.com/questions/27317069/collect-all-minimum-solutions-from-a-predicate). BTW, you seem to be re-writing predicates that are available in every Prolog (and have been for decades). — , Aug 25 '16 at 06:39
@coder This would be the last argument to `knapsack_go/4`, I guess. An example invocation of the program from the top level should be included in the question. — , Aug 25 '16 at 07:19
It seems that the last argument to knapsack_go/4, collects the overall profit but the list of the elements I think is amounts .I don't think that the knapsack would find all the possible solutions ,anyway I agree an example should be included... — coder, Aug 25 '16 at 07:34
Is add/3 a builtin of win-prolog ? and I think this could be simpler: `between(L,H,N) :- repeat(L,H,N).` — CapelliC, Aug 25 '16 at 17:13

score 2 · Accepted Answer · answered Aug 25 '16 at 19:26

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.

Thanks! I have one more question, with my add_list I receive the same thing once as [a,b,c] and another time as [a,b,c|_1111] - why is that? — Ariel Pinchover, Aug 25 '16 at 19:44
@Infested, for that I'm not sure because I wasn't able to run your code cause I'm using swi-prolog and it didn't recognize the repeat predicate so without running the program I can't see where the problem is. — coder, Aug 25 '16 at 19:53

Knapsack Find Max

1 Answers1