How to maximize the goal in prolog?

问题:

I am trying to solve the knapsack problem in prolog. Following is my implementation.

% 'ks' is compound term which has 4 argumets                                                                                                                                                                                                   
%   1 - List of items to be chosen from.                                                                                                                                                                                                       
%   2 - Maximum weight a knapsack can carry.                                                                                                                                                                                                   
%   3 - Selected items which sum of weights is less than or equal to knapsack capacity.                                                                                                                                                            
%   4 - The gain after choosing the selected item.                                                                                                                                                                                             


% base conditions where input list contains only one items and                                                                                                                                                                                 
% it is either selected or excluded.                                                                                                                                                                                                           
ks([item(W1, V1)], W, [item(W1, V1)], V1):- W1 =< W.
ks([item(W1, _)], W, [], 0):- W1 > W.

% An item from the input list is chosen in the knapsack.                                                                                                                                                                                       
% In that case, we recurse with smaller list with reduced weight constraint.                                                                                                                                                                  
ks(ItemList, MaxWeight, SelectItems, Gain) :-
    append(Prefix, [item(W1, V1)|Suffix], ItemList),
    append(Prefix, Suffix, RemList),
    NewWeight is MaxWeight - W1,
    W1 =< MaxWeight,
    append([item(W1, V1)], SelectItems1, SelectItems),
    ks(RemList, NewWeight, SelectItems1, Gain1),
    Gain is V1 + Gain1.

% An item from the input list is not chosen in the knapsack.                                                                                                                                                                                   
% In that case, we recurse with smaller list but with the same weight constraint.                                                                                                                                                             
ks(ItemList, MaxWeight, SelectItems, Gain) :-
    append([P1|Prefix], [item(W1, V1)|Suffix], ItemList),
    append([P1|Prefix], Suffix, RemList),
    not(member(item(W1, V1), SelectItems)),
        ks(RemList, MaxWeight, SelectItems, Gain).

The input to the program will be list of items as below. in term item(W, V) W is weight of the item while V is value of the item. Goal to maximize the value for the given weight constraint.

ks([item(2,3), item(3,4), item(4,5), item(5,8), item(9,10)], 20, List, Gain).
List = [item(2, 3), item(3, 4), item(4, 5), item(5, 8)],
Gain = 20 ;

While I am able to generate all the combinations of items with above program, I am not able to code to find out the maximum gain only.

Could any one please point me the right direction?

Thanks.

回答1:

I think that to find reusable abstractions it's an important point of studying programming. If we have a subset_set/2 that yields on backtracking all subsets, ks/4 becomes really simple:

subset_set([], _).
subset_set([H|T], Set) :-
  append(_, [H|Rest], Set),
  subset_set(T, Rest).

ks(Set, Limit, Choice, Gain) :-
    subset_set(Choice, Set),
    aggregate((sum(W), sum(G)), member(item(W, G), Choice), (TotWeight, Gain)),
    TotWeight =< Limit.

and then

ks_max(Items, Limit, Sel, WMax) :-
    aggregate(max(W,I), ks(Items,Limit,I,W), max(WMax,Sel)).

despite its simplicity, subset_set/2 is not really easy to code, and library available alternatives (subset/2, ord_subset/2) don't enumerate, but only check for the relation.

回答2:

There are at least two things you can do, depending on how you want to approach this.

You could simply collect all solutions and find the maximum. Something along the lines of:

?- Items = [item(2,3), item(3,4), item(4,5), item(5,8), item(9,10)],
   findall(Gain-List, ks(Items, 20, List, Gain), Solutions),
   sort(Solutions, Sorted),
   reverse(Sorted, [MaxGain-MaxList|_]).
% ...
MaxGain = 26,
MaxList = [item(9, 10), item(5, 8), item(4, 5), item(2, 3)].

So you find all solutions, sort them by Gain, and take the last. This is just one way to do it: if you don't mind collecting all solutions, it is up to you how you want to pick out the solution you need from the list. You might also want to find all maximum solutions: see this question and answers for ideas how to do that.

The cleaner approach would be to use constraints. As the comment to your questions points out, it is not very clear what you are actually doing, but the way to go would be to use a library like CLP(FD). With it, you could simply tell labeling/2 to look for the maximum Gain first (once you have expressed your problem in terms of constraints).

回答3:

greedy Approximation algorithm :

pw((P,W),Res) :-  PW is P/W, Res=(PW,P,W).
pws(Ps_Ws,PWs) :- maplist(pw,Ps_Ws,PWs).

sort_desc(List,Desc_list) :-
        sort(List,Slist),
        reverse(Slist,Desc_list).



ransack_([],_,_,[]).
ransack_([(_,P,W)|PWs],Const,Sum,Res) :-   
        Sum1 is W+Sum,
        Sum1 < Const ->
          Res=[(P,W)|Res1],
          ransack_(PWs,Const,Sum1,Res1)
        ;ransack_(PWs,Const,Sum,Res).                         


% ransack(+[(P,W)|..],+W,,Res)
ransack(L_PWs,W,Res) :- 
              pws(L_PWs,Aux),
              sort_desc(Aux,PWs),

              ransack_(PWs,W,0,Res).

Test

item(W, V)-->(V,W)

| ?- ransack([(3,2),(4,3),(5,4),(8,5),(10,9)],20,Res).
Res = [(8,5),(3,2),(4,3),(5,4)] ? ;
no