Решение задачи о рюкзаке: пусть An - объем предмета, Bn - стоимость предмета, объем рюкзака - V, n – число имеющихся предметов, m – число предметов, уложенных в рюкзак.
Требуется заполнить рюкзак так, чтобы суммарная стоимость предметов -> max, а объем не превосходил V.
Исходный код программы:
domains
pair=p(integer,integer,integer)%kazdii predmet budet predstavlen v vide p(Nomer,Objem,Stoimost)
pairs=pair*
zapolnenie=z(pairs,integer)%kazdoe zapolnenie ryukzaka bude predstavleno kak z(spisok predmetov, ih obshaya stoimost)
zapolneniya=zapolnenie*
predicates
nondeterm get(pair,pairs,pairs).
nondeterm permutation(integer,pairs,pairs).
sum(pairs,integer,integer).
nondeterm gen(pairs,integer,integer,zapolnenie).
max(zapolneniya, integer, integer).
solve(pairs,integer,integer).
find_all_max(zapolneniya,integer).
input(pairs,integer,integer).
input_list(integer,integer,pairs).
output(pairs).
clauses
%nuzno generit vse vozmoznie sochetaniya nashih predmetov na M mestah. Chto bi eto bili imenno
%sochetaniya, a ne peremesheniya (t.e kazdoe sochetanie vidavalos bi tolko odnazdi) vvedem uslovie,
%chto v spiske, zadayushem sochetanie, nomer kazdogo posledeyushego elementa bolshe nomera predidushego
%predicat get vibiraet proizvolnii element iz spiska i vozvrashaet spisok vseh elementov pravee vibrannogo
get(H,[H|Tail],Tail).%mozno vibrat golovu i togda hvost budet spisokm vseh elementov pravee vibrannogo
get(X,[_|Tail],NewTail):-get(X,Tail,NewTail).%a mozno rekursivno vibrat element iz hvosta spiska
%predicat, generiruyushii vse sochetaniya elementov spiska na M mestah
permutation(0,_,[]):-!.%esli kolichestvo mest=0, to otvetom mozet bit tolko pustoi spisok
permutation(N,Elements,[H|Tail]):-get(H,Elements,NewElements),%inache vibiraem iz spiska element H
N1=N-1,permutation(N1,NewElements,Tail).%posle chego stroim sochetanie iz N-1 elementa ostavsheisya chasti spiska
%predicat, schitayushii summarnii objem i summarnuyu stoimost zadannogo sochetaniya predmetov
sum([],0,0).%esli spisok pust, to i objem i stoimost ravni 0
sum([p(_,A,B)|Tail],V,C):-sum(Tail,V1,C1),V=V1+A,C=C1+B.%inache rekursivno schitaem summi hvosta
%i pribavlyaem nuznii znacheniya
%predicat, generyashii podhodyashee sochetanie predmetov i zapisivayushii ee stoimost
gen(Pairs,M,MaxV,z(L,C)):-permutation(M,Pairs,L),%generim prosto sochetanie
sum(L,V,C),V<=MaxV.%nahodim summarnii objem i summarnuyu stoimost.
%proveryaem ogranichenie objema i v zapominaem stoimost
%predicat, nahodyashii v spiske zapolnenii ryukzaka stoimost naibollie optimalnogo. Vtoroi parametr - tekushee maksimalnaya stoimost
max([],Z,Z).%esli ostalos prosmotret 0 vozmoznih kandidatov, to tekushee optimalnoe znachenie stanovitsya otvetom
max([z(_,Cost)|Tail],TempMaxCost,Ans):-Cost>TempMaxCost,!,max(Tail,Cost,Ans).%sravnivaem stoimost
%zapolneniya v golove spiska so stoimostyu tekushego optimalnogo zapolneniya. Esli ona bolshe, to golova spiska
%stanovitsya novoi tekushei maksimalnoi stoimostyu
max([_|Tail],TempMax,Ans):-max(Tail,TempMax,Ans).%esli ne bolshe (iz-za otsecheniya popadaem syuda tolko v etom sluchae),
%to rekursivno prodolzaem poisk v hvoste
%predicat, nahodyashii reshenie zadachi
solve(Pairs,M,MaxV):-findall(L,gen(Pairs,M,MaxV,L),Fillings),%nahodim spisok vshe podhodyashih zapolnenii
Fillings=[z(_,Cost)|Tail],!,%on ne pust
max(Tail,Cost,Max),find_all_max(Fillings,MaX).
solve(_,M,MaxV):-write("Nelzya vibrat nikakie ",M," predmeta(ov), chtobi ih objem ne previshal ",MaxV,".\n").
find_all_max([],_).
find_all_max([z(G,Cost)|Tail],Cost):-!,write("Nado vzyat predmeti s nomerami "),output(G),
write(". Obshaya stoimost predmetov: ",Cost),nl,find_all_max(Tail,Cost).
find_all_max([_|Tail],Cost):-find_all_max(Tail,COst).
%predicat schitivaniya spiska harakteristik predmetov s nomerami ot K do N
input_list(K,N,[]):-K=N+1,!.%esli K>N, to ostanavlivaemsya
input_list(K,N,[p(K,A,B)|Tail]):-write("Vvedite objem ",K," predmeta: "),readint(A),%inache schitivaem objem
write("Vvedite stoimost ",K," predmeta: "),readint(B),%schitivaem stoimost predmeta
K1=K+1,input_list(K1,N,Tail).%i rekursivno schitivaem harakteristiki ostalnih predmetov
%predicat schitivaniya vseh nachalnih dannih
input(L,M,V):-write("Vvedite kolichestvo dostupnih predmetov: "),readint(N),
input_list(1,N,L),write("Vvedite kakoe kolichestvo predmetov neobhodimo ulozit: "),
readint(M),write("Vvedite maksimalnii objem: "),readint(V).
%predicat vivoda otveta na ekran. Vivoditsya tolko nomer predmetam kotorii vhodit v optimalnoe zapolnenie
output([]).
output([p(N,_,_)|Tail]):-write(N,' '),output(Tail).
goal
input(L,M,V),!,solve(L,M,V).
2ая версия:
domains
pair=p(integer,integer,integer)%kazdii predmet budet predstavlen v vide p(Nomer,Objem,Stoimost)
pairs=pair*
zapolnenie=z(pairs,integer)%kazdoe zapolnenie ryukzaka bude predstavleno kak z(spisok predmetov, ih obshaya stoimost)
zapolneniya=zapolnenie*
predicates
nondeterm get(pair,pairs,pairs).
nondeterm permutation(integer,pairs,pairs).
sum(pairs,integer,integer).
nondeterm for(integer,integer,integer).
nondeterm gen(pairs,integer,integer,zapolnenie).
max(zapolneniya, integer, integer).
solve(pairs,integer).
find_all_max(zapolneniya,integer).
output(pairs).
length(pairs,integer).
clauses
%nuzno generit vse vozmoznie sochetaniya nashih predmetov na M mestah. Chto bi eto bili imenno
%sochetaniya, a ne peremesheniya (t.e kazdoe sochetanie vidavalos bi tolko odnazdi) vvedem uslovie,
%chto v spiske, zadayushem sochetanie, nomer kazdogo posledeyushego elementa bolshe nomera predidushego
%predicat get vibiraet proizvolnii element iz spiska i vozvrashaet spisok vseh elementov pravee vibrannogo
get(H,[H|Tail],Tail).%mozno vibrat golovu i togda hvost budet spisokm vseh elementov pravee vibrannogo
get(X,[_|Tail],NewTail):-get(X,Tail,NewTail).%a mozno rekursivno vibrat element iz hvosta spiska
%predicat, generiruyushii vse sochetaniya elementov spiska na M mestah
permutation(0,_,[]):-!.%esli kolichestvo mest=0, to otvetom mozet bit tolko pustoi spisok
permutation(N,Elements,[H|Tail]):-get(H,Elements,NewElements),%inache vibiraem iz spiska element H
N1=N-1,permutation(N1,NewElements,Tail).%posle chego stroim sochetanie iz N-1 elementa ostavsheisya chasti spiska
%predicat, schitayushii summarnii objem i summarnuyu stoimost zadannogo sochetaniya predmetov
sum([],0,0).%esli spisok pust, to i objem i stoimost ravni 0
sum([p(_,A,B)|Tail],V,C):-sum(Tail,V1,C1),V=V1+A,C=C1+B.%inache rekursivno schitaem summi hvosta
%i pribavlyaem nuznii znacheniya
%predicat, generyashii shislo iz zadannogo diapazona [A,B]
for(A,A,_).%chislo A podhodit
for(I,A,B):-A
%predicat, generyashii podhodyashee sochetanie predmetov i zapisivayushii ee stoimost
gen(Pairs,N,MaxV,z(L,C)):-for(M,1,N),%budem rassmatrivat zapolneniya iz M predmetov, gde M probegaet znacheniya ot 1 do N
permutation(M,Pairs,L),%generim prosto sochetanie
sum(L,V,C),V<=MaxV.%nahodim summarnii objem i summarnuyu stoimost.
%proveryaem ogranichenie objema i v zapominaem stoimost
%predicat, nahodyashii v spiske zapolnenii ryukzaka stoimost naibollie optimalnogo. Vtoroi parametr - tekushee maksimalnaya stoimost
max([],Z,Z).%esli ostalos prosmotret 0 vozmoznih kandidatov, to tekushee optimalnoe znachenie stanovitsya otvetom
max([z(_,Cost)|Tail],TempMaxCost,Ans):-Cost>TempMaxCost,!,max(Tail,Cost,Ans).%sravnivaem stoimost
%zapolneniya v golove spiska so stoimostyu tekushego optimalnogo zapolneniya. Esli ona bolshe, to golova spiska
%stanovitsya novoi tekushei maksimalnoi stoimostyu
max([_|Tail],TempMax,Ans):-max(Tail,TempMax,Ans).%esli ne bolshe (iz-za otsecheniya popadaem syuda tolko v etom sluchae),
%to rekursivno prodolzaem poisk v hvoste
%predicat nahozdeniya dlini spiska
length([],0).%esli pustoi, to ona ravna 0
length([_|Tail],N):-length(Tail,N1),N=N1+1.%inache schitaem dlinu hvosta i pribavlyaem 1
%predicat, nahodyashii reshenie zadachi
solve(Pairs,MaxV):-length(Pairs,N),findall(L,gen(Pairs,N,MaxV,L),Fillings),%nahodim spisok vshe podhodyashih zapolnenii
Fillings=[z(_,Cost)|Tail],!,%on ne pust
max(Tail,Cost,Max),find_all_max(Fillings,MaX).
solve(_,MaxV):-write("Nelzya vibrat nikakoi predmet, chtobi ego objem ne previshal ",MaxV,".\n").
find_all_max([],_).
find_all_max([z(G,Cost)|Tail],Cost):-!,write("Nado vzyat predmeti s nomerami "),output(G),
write(". Obshaya stoimost predmetov: ",Cost),nl,find_all_max(Tail,Cost).
find_all_max([_|Tail],Cost):-find_all_max(Tail,COst).
%predicat vivoda otveta na ekran. Vivoditsya tolko nomer predmetam kotorii vhodit v optimalnoe zapolnenie
output([]).
output([p(N,_,_)|Tail]):-write(N,' '),output(Tail).
goal
L=[p(1,1,2),p(2,1,3),p(3,2,7),p(4,2,1),p(5,1,3)],solve(L,3).
|
Главная
Каталог файлов
