Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 62809
Создание отчето... 62807
ТЕХНОЛОГИИ ДОСТ... 59343
Пример работы с... 58066
Имитационное мо... 54734
Реклама
http://banketnedorogo.ru/ заказать горку из бокалов шампанского.
Сейчас на сайте
Гостей: 14
На сайте нет зарегистрированных пользователей

Пользователей: 13,073
новичок: DENIS1996
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Метод конечных разностей для интерполяции/экстраполяции на Delphi
Моделирование работы узла коммутации сообщений на GPSS + Пояснительная з...
Моделирование работы обрабатывающего участка цеха в GPSS

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Задача о укладке вещей в рюкзаке
Решение задачи о рюкзаке: пусть 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).


Опубликовал Kest February 22 2011 22:24:41 · 0 Комментариев · 7321 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
3d Tank [Исходник...
PHP 5 для "чайников"
Секреты программи...
Delphi 6/7 базы д...
Проигрыватель Mp3
Gold Submitter II...
Midi
Пятнашки и крести...
База для Allsubmi...
Delphi 2005. Разр...
PHP5. Профессиона...
Создание лабиринт...
ComboBox97
Xrumer 4 Platinum...
PHP: Полезные приемы
База данных: Книж...
Delphi. Разработк...
TsHintManager
SysInfo [Исходник...
Comdrv

Топ загрузок
Приложение Клие... 100422
Delphi 7 Enterp... 84951
Converter AMR<-... 20062
GPSS World Stud... 11971
Borland C++Buil... 11406
Borland Delphi ... 8379
Turbo Pascal fo... 7008
Visual Studio 2... 4985
Калькулятор [Ис... 4630
FreeSMS v1.3.1 3530
Случайные статьи
Процедура SetGraph...
Учитесь у плотников
Установка фотограф...
Коллекция диалогов
Вычислить произвед...
Занятие 3
QueryInterface и I...
Батуты в СПб попры...
Обозначения
Определение вторич...
Задание на моделир...
Выбор ключа итерации
Настройки приватности
Различные команды ...
Перегрузка методов...
Закругленные уголк...
Создание пользоват...
У истоков трафа ча...
Умноженные векторы...
2.1. Вездесущий дв...
Изменение последов...
0 для совместимост...
Группы
функции-члены
от его имени
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?