The Knap-Sack Problem

The first problem we will consider is the knap-sack problem. The idea is that we have a knap-sack and a bunch of things of various sizes to put in it. The question is whether there is a subset of the things that will fit exactly into the knap-sack. The problem can be formally stated as follows:

Given n items, each of integer size k_i $(1 \le i \le n)$, and a knap-sack of size K. 1) determine whether there is a subset of the items that sums to K. 2) Find such a subset.

We will represent the items and their sizes by using a set of facts item/2, where item(3,5) would mean that the third item is of size 5.

To determine whether there is a subset of items that exactly fill the knap-sack, we can just nondeterministicaly try all alternatives.

% ks(+I,+K) if there is a subset of items 1,...,I that sums to K.
ks(0,0).               % the empty set sums to 0
ks(I,K) :- I>0,        % don't include this Ith element in the knapsack
    I1 is I-1, ks(I1,K).
ks(I,K) :- I>0,        % do include this Ith element in the knapsack
    item(I,Ki), K1 is K-Ki, K1 >= 0, I1 is I-1, ks(I1,K1).

The first clause says that the empty set takes no space in the sack. The second clause covers the case in which the Ith item is not included in the sack. The third clause handles the case in which the Ith item is included in the sack.

This program could be exponential in the number of items, since it tries all subsets of items. However, there are only I² possible distinct calls to ks/2, so tabling will make this polynomial.

This program just finds whether a packing of the knapsack exists; it doesn't return the exact set of items that fit. We could simply add a third argument to this definition of ks/2 which would be the list of items added to the knap-sack. But that might then build an exponential-sized table. For example with every item of size one, there are exponentially many items to include to make a sum. So instead of simply adding another parameter and tabling that predicate, we will use ks/2 to avoid constructing a table unnecessarily. Note that this is similar to how we constructed a parse tree for a grammar by using the recognizer. Notice that ksp/3 uses ks/2 in its definition.

ksp(0,0,[]).
ksp(I,K,P) :- I>0,
    I1 is I-1, ks(I1,K),
    ksp(I1,K,P).
ksp(I,K,[I|P]) :- I>0,
    item(I,Ki), K1 is K-Ki, K1 >= 0, I1 is I-1, ks(I1,K1),
    ksp(I1,K1,P).

(There is something going on here. Can we figure out a syntax or conventions to make this uniform?)

% ks(+I,+K) if there is a subset of items 1,...,I that sums to K.
ks(0,0).
ks(I,K) :- ks1(I,K,_).
  ks1(I,K,I1) :- I>0,I1 is I-1, ks(I1,K).
ks(I,K) :- ks2(I,K,_).
  ks2(I,K,I1) :- I>0, item(I,Ki), K1 is K-Ki, K1 >= 0, I1 is I-1, ks(I1,K1).

ksp(0,0,[]).
ksp(I,K,P) :- ks1(I,K,I1), ksp(I1,K,P).
ksp(I,K,[I|P]) :- ks2(I,K,I1), ksp(I1,K1,P).