79 lines
2.0 KiB
Prolog
79 lines
2.0 KiB
Prolog
:- use_module(library(simplex)).
|
|
|
|
knapsack :-
|
|
L = [
|
|
(map, 9, 150),
|
|
(compass, 13, 35),
|
|
(water, 153, 200),
|
|
(sandwich, 50, 160),
|
|
(glucose, 15, 60),
|
|
(tin, 68, 45),
|
|
(banana, 27, 60),
|
|
(apple, 39, 40),
|
|
(cheese, 23, 30),
|
|
(beer, 52, 10),
|
|
('suntan cream', 11, 70),
|
|
(camera, 32, 30),
|
|
('t-shirt', 24, 15),
|
|
(trousers, 48, 10),
|
|
(umbrella, 73, 40),
|
|
('waterproof trousers', 42, 70),
|
|
('waterproof overclothes', 43, 75),
|
|
('note-case',22, 80),
|
|
(sunglasses, 7, 20),
|
|
(towel, 18, 12),
|
|
(socks, 4, 50),
|
|
(book, 30, 10 )],
|
|
gen_state(S0),
|
|
length(L, N),
|
|
numlist(1, N, LN),
|
|
time(( create_constraint_N(LN, S0, S1),
|
|
maplist(create_constraint_WV, LN, L, LW, LV),
|
|
constraint(LW =< 400, S1, S2),
|
|
maximize(LV, S2, S3)
|
|
)),
|
|
compute_lenword(L, 0, Len),
|
|
sformat(A1, '~~w~~t~~~w|', [Len]),
|
|
sformat(A2, '~~t~~w~~~w|', [4]),
|
|
sformat(A3, '~~t~~w~~~w|', [5]),
|
|
print_results(S3, A1,A2,A3, L, LN, 0, 0).
|
|
|
|
|
|
create_constraint_N([], S, S).
|
|
|
|
create_constraint_N([HN|TN], S1, SF) :-
|
|
constraint(integral(x(HN)), S1, S2),
|
|
constraint([x(HN)] =< 1, S2, S3),
|
|
constraint([x(HN)] >= 0, S3, S4),
|
|
create_constraint_N(TN, S4, SF).
|
|
|
|
create_constraint_WV(N, (_, W, V), W * x(N), V * x(N)).
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
%
|
|
compute_lenword([], N, N).
|
|
compute_lenword([(Name, _, _)|T], N, NF):-
|
|
atom_length(Name, L),
|
|
( L > N -> N1 = L; N1 = N),
|
|
compute_lenword(T, N1, NF).
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
%
|
|
print_results(_S, A1, A2, A3, [], [], WM, VM) :-
|
|
sformat(W1, A1, [' ']),
|
|
sformat(W2, A2, [WM]),
|
|
sformat(W3, A3, [VM]),
|
|
format('~w~w~w~n', [W1,W2,W3]).
|
|
|
|
|
|
print_results(S, A1, A2, A3, [(Name, W, V)|T], [N|TN], W1, V1) :-
|
|
variable_value(S, x(N), X),
|
|
( X = 0 -> W1 = W2, V1 = V2
|
|
; sformat(S1, A1, [Name]),
|
|
sformat(S2, A2, [W]),
|
|
sformat(S3, A3, [V]),
|
|
format('~w~w~w~n', [S1,S2,S3]),
|
|
W2 is W1 + W,
|
|
V2 is V1 + V),
|
|
print_results(S, A1, A2, A3, T, TN, W2, V2).
|