% 0-1 knapsack no SICStus % (o número de variáveis deverá ser pequeno) :- use_module(library(clpfd)). % Dominios Finitos solve(Ex) :- see(Ex), read(Objs), read(Pmax), seen, qsort(Objs,OObjs,[]), split(OObjs,Ps,Vs,Xs), restrknap01(Ps,Vs,Xs,Z,Pmax), labeling([maximize(Z),down],Xs), %clpfd write_sol(Z,Objs). % -- restricoes restrknap01(Ps,Vs,X,Z,Pmax) :- scalar_product(Ps,X,#=<, Pmax), %clpfd scalar_product(Vs,X,#=,Z), dominio(X). dominio([]). dominio([Xj|X]) :- Xj in {0,1}, dominio(X). % -- ordenar objectos por ordem decrescente de Vi/Pi qsort([],L,L). qsort([o(I,Xi,Pi,Vi)|Objs],Lo,Ro) :- Aux is Vi/Pi, partition(Objs,Aux,LM,Lm), qsort(LM,Lo,[o(I,Xi,Pi,Vi)|Lmo]), qsort(Lm,Lmo,Ro). partition([],_,[],[]). partition([o(I,Xi,Pi,Vi)|Objs],Q,[o(I,Xi,Pi,Vi)|ObjsM],Objsm) :- Aux is Vi/Pi, Aux > Q, !, partition(Objs,Q,ObjsM,Objsm). partition([ObjI|Objs],Q,ObjsM,[ObjI|Objsm]) :- partition(Objs,Q,ObjsM,Objsm). % -- separar informacao relativa aos objectos split([],[],[],[]). split([o(_,Xi,Pi,Vi)|Os],[Pi|Ps],[Vi|Vs],[Xi|Xs]) :- split(Os,Ps,Vs,Xs). % -- escrever solucao write_sol(Z,Objs) :- write('Valor '), write(Z), nl, write_sol_(Objs), nl. write_sol_([]). write_sol_([o(I,1,_,_)|Objs]) :- !, write(I), put(32), write_sol_(Objs). write_sol_([_|Objs]) :- write_sol_(Objs). /* %----------------------------------------- % Conteúdo do Ficheiro de dados %------------------------------------------ [o(1,_,41,85),o(2,_,32,72),o(3,_,24,61),o(4,_,17,45),o(5,_,15,37)]. 65. */