prolog basket(L,Smin,Smax,S)

Question

here have a problem with Prolog. Consider a set of products, each with a given price. For simplicity we think of one item of each product. Assume you have a list of pairs, (Item,Price), representing names of items in a store and their corresponding price. The name is a constant and the price is a positive integer number. For example:

[(radio,130),(tv,940),(laptop,400),(bicycle,330)]

Write a predicate basket(L,Smin,Smax,S) that finds a subset S of the items available in L such that the sum of the prices in S is higher that Smin and lower than Smax. All possible subsets that meet the specification of the problem should be presented one by one, through backtracking!

Hi there. The docs on [how to ask homework questions](http://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions) say: "Make a good faith attempt to solve the problem yourself first. If we can't see enough work on your part your question will likely be booed off the stage; it will be voted down and closed." Please post code. — Ryan Bigg, Jan 06 '16 at 20:15

Willem Van Onsem · Accepted Answer · 2016-01-06T18:05:19.293

A practice in Prolog that eases things most of the time is using an accumulator. An accumulator is a variable you pass recursively and update in each recursive step. Each recursive step can inspect the value of the variable and decide accordingly. Here the accumulator is the sum of the price of the items this far added to S. Evidently at the start, that sum is zero, so we first ease things a bit by introducing an accumulator:

basket(L,Smin,Smax,S) :-
    basket(L,Smin,Smax,0,S).

Now we need to work out basket/5. There is a base case in which all items are enumerated. Therefore L is empty. What we need to do then, is check whether the Sum is between the given bounds:

basket([],Smin,Smax,Sum,[]) :-
    Smin < S,
    S < Smax.

This is the only base case. Note that S (the last argument) is the empty list as well. Since all items have already been inspected, this means we will not add any elements to the tail of the subset.

Now there are two recursive cases. In the recursive case, L contains at least one element, and we can do two things:

either we accept that item, and add it to our subset;
or we discard the item, and continue further.

In case we accept the item, the predicate looks like:

basket([(I,V)|T],Smin,Smax,Sum,[(I,V)|S]) :-
    Sum1 is Sum+V,
    Sum1 < Smax,
    basket(T,Smin,Smax,Sum1,S).

We thus decide to add the element, we calculate the new sum Sum1 by adding the value V to the original Sum, we can (optionally) already perform a bounds check on the upper bound of the value. This can be efficient if there is a large amount of items: we cut off search from the moment our bag will start to run in overflow.

Finally we have the other recursive case, where we simply decide to discard the item. This is an easy one:

basket([_|T],Smin,Smax,Sum,S) :-
    basket(T,Smin,Smax,Sum,S).

We don't even look at the head, we simply take the tail of the list feeded to basket, we do not have to update Sum, since nothing changed to the subset.

Putting it all together, the following program should do the trick:

basket(L,Smin,Smax,S) :-
    basket(L,Smin,Smax,0,S).

basket([],Smin,Smax,Sum,[]) :-
    Smin < S,
    S < Smax.
basket([(I,V)|T],Smin,Smax,Sum,[(I,V)|S]) :-
    Sum1 is Sum+V,
    Sum1 < Smax,
    basket(T,Smin,Smax,Sum1,S).
basket([_|T],Smin,Smax,Sum,S) :-
    basket(T,Smin,Smax,Sum,S).

Note however that using dynamic programming one can generate solutions way more efficiently.

score 1 · Answer 2 · edited May 23 '17 at 12:31

when we have sublist/2 from this answer

sublist([], []).
sublist([_|XS], YS) :-
    sublist(XS, YS).
sublist([X|XS], [X|YS]) :-
    sublist(XS, YS).

library(aggregate) can be used to enforce the constraint:

basket(L,Smin,Smax,S) :-
    sublist(L,S),
    aggregate(sum(P), I^member((I,P),S), T),
    T>=Smin,T=<Smax.

?- basket([(radio,130),(tv,940),(laptop,400),(bicycle,330)],1600,2000,S).
S = [(tv, 940),  (laptop, 400),  (bicycle, 330)] ;
S = [(radio, 130),  (tv, 940),  (laptop, 400),  (bicycle, 330)].

prolog basket(L,Smin,Smax,S)

2 Answers2