The knapsack problem in prolog

Help!
1

Hello,

we have to solve the knapsack problem in Prolog at the university. We have the source code as a solution, but we have to explain it.
Can someone explain the functions to me?
Thank you very much.

I’m using: SWI-Prolog version 8.0.2

My code :

item(1,12,4).
item(2,2,2).
item(3,2,1).
item(4,1,1).
item(5,4,10).

weight([],0).
weight([item(,W,) | Rest], X) :-
weight(Rest,RestW),
X is W + RestW.

value([],0).
value([item(,,V) | Rest], X) :-
value(Rest,RestV),
X is V + RestV.

subseq([],[]).
subseq([Item | RestX], [Item | RestY]) :-
subseq(RestX,RestY).
subseq(X, [_ | RestY]) :-
subseq(X,RestY).

legalKnapsack(Number,Capacity,Knapsack):-
subseq(Knapsack,Number),
weight(Knapsack,W),
W =< Capacity.

allLegalKnapsacks(Number,Capacity,ListOfLegalKnapsacks) :-
findall(LegalKnapsack, legalKnapsack(Number,Capacity,LegalKnapsack), ListOfLegalKnapsacks).

maximumValue([LEGAL | LEGALS], MAXVAL) :- value(LEGAL, VAL), maxVal(LEGALS, VAL, LEGAL, MAXVAL).

maxVal([], MAXVAL, MAXVALLEGAL,MAXVALLEGAL).
maxVal([LEGAL | LEGALS], MAXVAL, MAXVALLEGAL, OUTPUT) :- value(LEGAL, NEWVAL), NEWVAL > MAXVAL,
maxVal(LEGALS, NEWVAL, LEGAL, OUTPUT).
maxVal([LEGAL | LEGALS], MAXVAL, MAXVALLEGAL, OUTPUT) :- value(LEGAL, NEWVAL), NEWVAL =< MAXVAL,
maxVal(LEGALS, MAXVAL, MAXVALLEGAL, OUTPUT).

knapsackOptimization(Number, Capacity, Knapsack) :- allLegalKnapsacks(Number, Capacity, R),
maximumValue(R, Knapsack),
value(Knapsack, VAL),print(’\n’),print('Value: '), print(VAL).

2

brooki

    May 28

Hello,

we have to solve the knapsack problem in Prolog at the university. We have the source code as a solution, but we have to explain it.
Can someone explain the functions to me?

Thank you for at least being honest that you want us to do your homework for you. (In my day that was called “cheating”.)

You are unlikely to find someone here who will just do all the work for you. A better approach, more likely of getting useful replies, is to tell us what you have done so far and where you got stuck.

If, as I suspect, you have done nothing so far, then maybe you should put forth some effort to read the textbook and acquire a clue or two. If that is beyond you then consider hiring a tutor (many of whom will help you cheat if you pay them adequately).

One thing you might want to try is to run the code on small examples while tracing it, using gtrace.

3

Hello, my question was very short and poorly worded. Of course we have already dealt with the code. We have understood everything except this one:

“maxVal([], MAXVAL, MAXVALLEGAL,MAXVALLEGAL).
maxVal([LEGAL | LEGALS], MAXVAL, MAXVALLEGAL, OUTPUT) :- value(LEGAL, NEWVAL), NEWVAL > MAXVAL,
maxVal(LEGALS, NEWVAL, LEGAL, OUTPUT).
maxVal([LEGAL | LEGALS], MAXVAL, MAXVALLEGAL, OUTPUT) :- value(LEGAL, NEWVAL), NEWVAL =< MAXVAL,
maxVal(LEGALS, MAXVAL, MAXVALLEGAL, OUTPUT).”

can someone help me understand this passage easier?
thank you.

4

maxVal is a rule which is defined over 3 clauses. For a particular set of inputs only 1 clause will match.
If the initial argument is an empty list, only the first clause matches.
If the initial argument is not an empty list, then potentially two clauses match, however those clauses differ by having a ‘guard’ of NEWVAL>MAXVAL and NEWVAL =< MAXVAL, which cannot both be true, so only 1 of these clauses will match.
Note that the rules with a non-empty list call themselves with a smaller list. The maxVal rule is initially triggered by the maximumValue clause. This should give you an idea of what information the rules are attempting to discover.