Knapsack problem in Prolog

The knapsack problem is a very common programming problem that has been solved 1001 times using twice as much programming languages. I did it in Prolog, with a bit of help from my good friend Google 🙂

Image from Wikipedia.org

Image from Wikipedia.org

So, the first thing we do is represent our pantry (the stuff we can pick from). One way to go about doing this is by representing it in a functor food where we have the name, the weight and the calories.

food(bread,4,9200),
food(pasta,2,4500),
food(peanutButter,1,6700),
food(babyFood,3,6900)

A solution to our problem would consist of a list of these items. For example:  [food(bread, 4, 9200), food(pasta, 2, 4500)]. This is a solution with 13700 calories and a total weight of 6. To calculate these things we’ll have the following predicates:

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

calories([],0).
calories([food(_,_,C) | Rest], X) :-
  calories(Rest,RestC),
  X is C + RestC.

They are pretty straight forward. We take the weight/calories of the first element and add it to the result of our recursive call.

Now we have to generate all possible solutions of combinations we can put in our knapsack. This can be all elements, the first, the second, the third,.., the first and second,.. We need all possible sublists. Yay, we can do this!

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

So, if we have a given list, and a possible sublist, how do we check if the latter is an actual sublist?

First clause: both the first elements of the list are the same. We can discard those, and call ourselved recursively.
Second clause: the first two elements differ, but our sublist could start somewhere in the middle! So we discard our first element of our list which we check if it contains our sublist and call ourselves recusively.

Of course, we all know (duh) that we can use these predicates to tell us all subsequences of the given list. So we could do something like this:

?- subseq(R, [1, 2, 3]).
R = [1, 2, 3] ;
R = [1, 2] ;
R = [1, 3] ;
R = [1] ;
R = [2, 3] ;
R = [2] ;
R = [3] ;
R = [].

Next we need to decide if, given a list of pantry, it is “legal” to put in our knapsack. Legal meaning that it has to meet our constraint: it can’t exceed the given capacity:

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

This is pretty legit stuff. We check if it’s a subsequence of our initial pantry. If the weight does not exceed the given capacity we can carry this. To produce a list of legal pantry items we use this little function:

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

It uses the findall predicate. This takes a goal,  a variable to unify with if we found something that satisfies our goal and a list to accumulate all the instances that satisfy our goal, ListOfLegalKnapsacks. Now that we have all the little predicates to generate all our legal pantry lists, we have to determine the one with the maximum calories. Omnomnom. Therefore we have the following predicate:

maximumCalories([LEGAL | LEGALS], MAXCALS) :- calories(LEGAL, CALS), maxCals(LEGALS, CALS, LEGAL, MAXCALS).

maxCals([], MAXCALS, MAXCALLEGAL, MAXCALLEGAL).
maxCals([LEGAL | LEGALS], MAXCALS, MAXCALLEGAL, OUTPUT) :- calories(LEGAL, NEWCALS), NEWCALS > MAXCALS,
                                                           maxCals(LEGALS, NEWCALS, LEGAL, OUTPUT).
maxCals([LEGAL | LEGALS], MAXCALS, MAXCALLEGAL, OUTPUT) :- calories(LEGAL, NEWCALS), NEWCALS =< MAXCALS,
                                                           maxCals(LEGALS, MAXCALS, MAXCALLEGAL, OUTPUT).

When we we unify a list of legal pantry lists we traverse them one by one. We first calculate the calories of our first list in maximumCalories. Then we check it with maxCals. This is pretty straightforward stuff. We check to see if every next item in the list has more calories. If not, we skip it and check the next one. This will determine the sublist with the most calories.

I guess we’re there. Let’s give it a whirl with this predicate:

knapsackOptimization(Pantry, Capacity, Knapsack) :- allLegalKnapsacks(Pantry, Capacity, R),
                                                    maximumCalories(R, Knapsack),
                                                    calories(Knapsack, CALS),print('\n'),print('Calories: '), print(CALS).

A sample query would be the following:

knapsackOptimization([food(bread,4,9200),food(pasta,2,4500),food(peanutButter,1,6700),food(babyFood,3,6900)],4,Knapsack).

This should return the following output:

?- knapsackOptimization([food(bread,4,9200),food(pasta,2,4500),food(peanutButter,1,6700),food(babyFood,3,6900)],4,Knapsack).

Calories: 13600
Knapsack = [food(peanutButter, 1, 6700), food(babyFood, 3, 6900)]

Yuck, babyfood!

That’s it guys!

Christophe,