Knapsack Problems (Dynamic Programming)

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than some given weight and the total value is as large as possible. The 0-1 knapsack problem restricts the number of each item to zero or one.

/* knap01(Set, MaximumWeight, Subset) is true if Set is a list of items      */
/*   a(Value,Weight) and the list Subset is a subset of Set such that the    */
/*   sum of the values in the Subset is maximized and the sum of the weights */
/*   in the Subset is less than or equal to MaximumWeight.                   */
/* e.g. knap01([a(6,1),a(10,2),a(12,3)], 5, X). gives X=[a(10,2),a(12,3)]    */
knap01(Set, MaximumWeight, Subset):-
  replicate(MaximumWeight, 0, FirstRow),
  knap01_1(Set, MaximumWeight, [0|FirstRow], [], [LastRow|Table]),
  reverse(Set, ReversedSet),
  knap01_3(Table, LastRow, MaximumWeight, ReversedSet, ReversedSubset),
  reverse(ReversedSubset, Subset).

knap01_1([], _, PreviousRow, Table, [PreviousRow|Table]).
knap01_1([a(Value,Weight)|Set], MaximumWeight, PreviousRow, Table0, Table):-
  knap01_2(1, MaximumWeight, Value, Weight, PreviousRow, NextRow),
  knap01_1(Set, MaximumWeight, [0|NextRow], [PreviousRow|Table0], Table).

knap01_2(I, MaximumWeight, _, _, _, []):-
  I > MaximumWeight, !.
knap01_2(I, MaximumWeight, Value, Weight, PreviousRow, [Item|NextRow]):-
  I_Weight is I - Weight,
  I_Weight >= 0,
  nth_member(PreviousRow, I_Weight, Item1),
  Item is Value + Item1,
  nth_member(PreviousRow, I, Item2),
  Item2 < Item, !,
  I1 is I + 1,
  knap01_2(I1, MaximumWeight, Value, Weight, PreviousRow, NextRow).
knap01_2(I, MaximumWeight, Value, Weigth, PreviousRow, [Item|NextRow]):-
  nth_member(PreviousRow, I, Item), !,
  I1 is I + 1,
  knap01_2(I1, MaximumWeight, Value, Weigth, PreviousRow, NextRow).

knap01_3([], _, _, _, []).
knap01_3([PreviousRow|Table], NextRow, I, [Item|Set], [Item|Subset]):-
  Item=a(_,Weight),
  nth_member(NextRow, I, NextRow_I),
  nth_member(PreviousRow, I, PreviousRow_I),
  NextRow_I \= PreviousRow_I, !,
  I1 is I - Weight,
  knap01_3(Table, PreviousRow, I1, Set, Subset).
knap01_3([PreviousRow|Table], _, I, [_|Set], Subset):-
  knap01_3(Table, PreviousRow, I, Set, Subset).
  
/* knap(Set, MaximumWeight, Collection) is true if Set is a list of items    */
/*   a(Value,Weight) and the list Collection contains elements from Set,     */
/*   possibly with repeats, such that the sum of the values in the           */
/*   Collection is maximized and the sum of the weights in the Collection is */
/*   less than or equal to MaximumWeight.                                    */
/* e.g. knap([a(11,6),a(7,4),a(5,3),a(1,1)], 25, X).                         */
/*   gives X=[a(11,6),a(11,6),a(11,6),a(7,4),a(5,3)]                         */
knap(Set, MaximumWeight, Collection):-
  replicate(MaximumWeight, 0, FirstRow),
  knap_1(Set, MaximumWeight, [0|FirstRow], [], [LastRow|Table]),
  reverse(Set, ReversedSet),
  knap_3(MaximumWeight, Table, LastRow, ReversedSet, ReversedCollection),
  reverse(ReversedCollection, Collection).

knap_1([], _, PreviousRow, Table, [PreviousRow|Table]).
knap_1([a(Value,Weight)|Set], MaximumWeight, PreviousRow, Table0, Table):-
  knap_2(1, MaximumWeight, Value, Weight, [0], PreviousRow, NextRow),
  knap_1(Set, MaximumWeight, [0|NextRow], [PreviousRow|Table0], Table).

knap_2(I, MaxWeight, _, _, _, _, []):-
  I > MaxWeight, !.
knap_2(I, MaxWeight, Value, Weight, RowSoFar, PrevRow, [Item|NextRow]):-
  % RowSoFar is the reversed list of elements so far in the next
  %   row except that 0 is appended as its first element (at the end)
  I_Weight is I - Weight,
  I_Weight >= 0,
  Weight_1 is Weight - 1,
  nth_member(RowSoFar, Weight_1, Item1),
  Item is Value + Item1,
  nth_member(PrevRow, I, Item2),
  Item2 < Item, !,
  I1 is I + 1,
  knap_2(I1, MaxWeight, Value, Weight, [Item|RowSoFar], PrevRow, NextRow).
knap_2(I, MaxWeight, Value, Weight, RowSoFar, PrevRow, [Item|NextRow]):-
  nth_member(PrevRow, I, Item), !,
  I1 is I + 1,
  knap_2(I1, MaxWeight, Value, Weight, [Item|RowSoFar], PrevRow, NextRow).

knap_3(0, _, _, _, []):-!.
knap_3(I, [PreviousRow|Table], NextRow, [_|Set], Collection):-
  nth_member(NextRow, I, Item),
  nth_member(PreviousRow, I, Item), !,
  knap_3(I, Table, PreviousRow, Set, Collection).
knap_3(I, Table, NextRow, Set, [Item|Collection]):-
  Set=[Item|_],
  Item=a(_,Weight),
  I1 is I - Weight,
  knap_3(I1, Table, NextRow, Set, Collection).

/* nth_member(+Xs, ?N, ?X) is true if X is the N-th (base 0) element of the  */
/*   list Xs.                                                                */
nth_member(Xs, N, X):-nth_member_1(Xs, X, 0, N).

nth_member_1([X|_], X, I, I).
nth_member_1([_|Xs], X, I0, I):-
  I1 is I0 + 1,
  nth_member_1(Xs, X, I1, I).
  
/* replicate(N, X, Xs) is true if the list Xs contains N occurrences of the  */
/*   item X.                                                                 */
replicate(0, _, []):-!.  
replicate(I, X, [X|Xs]):-
  I > 0,
  I1 is I - 1,
  replicate(I1, X, Xs).

/* reverse(Xs, Ys) is true if Ys is the result of reversing the order of the */
/*   elements in the list Xs.                                                */
%reverse(Xs, Ys):-reverse_1(Xs, [], Ys).

%reverse_1([], As, As).
%reverse_1([X|Xs], As, Ys):-reverse_1(Xs, [X|As], Ys).

% This goal gives:
%   Subset=[a(49,21),a(23,1),a(21,4),a(37,2),a(21,2),a(38,12),a(17,1),a(5,4),
%           a(32,3),a(28,11),a(25,13),a(22,9),a(15,8),a(39,5),a(3,0),a(31,4)]
test(Subset):-
  Set=[a(49,21),a(23, 1),a(21, 4),a(37, 2),a(28,28),a(27,47),a(21, 2),a( 6,23),
       a(38,12),a( 7,12),a(11,45),a(23,29),a(27,36),a(15,43),a(17, 1),a(17,38),
       a( 5, 4),a(41,33),a(32,18),a(32, 3),a(21,38),a(28,11),a( 0,35),a(25,13),
       a(30,29),a( 5, 3),a(11,32),a(41,26),a(28,21),a(42,47),a(22, 9),a(35,29),
       a(13,26),a(14,47),a(46,46),a( 2,19),a(34,30),a(32,34),a(15, 8),a(48,48),
       a(39, 5),a( 3, 0),a(40,45),a(28,20),a(16,22),a(17,40),a(31, 4),a(19,49)],
  knap01(Set, 100, Subset).

LPA Index     Home Page