How to maximize the goal in prolog?

2
votes
How to maximize the goal in prolog? - Stack Overflow
Asked
Active 5 years, 11 months ago
Viewed 526 times
2

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.

Improve this question
4
  • 2
    I find your code very confusing, and it not ever seems to be a knapsack problem. First 2 clauses what should do ? Try to describe them in plain English
    – CapelliC
    Feb 16 2016 at 7:21
  • @CapelliC I have added the comments with explanation. Let me know if it needs more commenting.
    – UnSat
    Feb 16 2016 at 15:54
  • 1
    good job. If your Prolog has library(aggregate), you could write ks_max(Items, Limit, Sel, WMax) :- aggregate(max(W,I), ks(Items,Limit,I,W), max(WMax,Sel)).
    – CapelliC
    Feb 16 2016 at 16:03
  • @CapelliC I am using SWI Prolog and it has aggregate library and your solution worked perfectly. Thank you.
    – UnSat
    Feb 16 2016 at 16:27
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.

Improve this answer
    1

    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).

    Improve this answer
      0

      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
      Improve this answer
      2
      • In your example run, the result is not the optimal one. The optimal result is [(8,5),(3,2),(10,9),(5,4)] .
        – UnSat
        Feb 16 2016 at 16:58
      • 1
        greedy algorithm not the optimal but the fast :)
        – Ans Piter
        Feb 16 2016 at 17:05

      Your Answer

      By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

      Not the answer you're looking for? Browse other questions tagged or ask your own question.

      Your privacy

      By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.

       
      3
      prolog
      I find your code very confusing, and it not ever seems to be a knapsack problem. First 2 clauses what should do ? Try to describe them in plain English – CapelliC
      @CapelliC I have added the comments with explanation. Let me know if it needs more commenting. – UnSat
      good job. If your Prolog has library(aggregate), you could write ks_max(Items, Limit, Sel, WMax) :- aggregate(max(W,I), ks(Items,Limit,I,W), max(WMax,Sel)). – CapelliC
      @CapelliC I am using SWI Prolog and it has aggregate library and your solution worked perfectly. Thank you. – UnSat

      3 Answers

      1
      votes

      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.

      1
      votes

      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).

      0
      votes

      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