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