Навигация
Главная
Поиск
Форум
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
21 ошибка прогр... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Имитационное мо... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Реклама
Сейчас на сайте
Гостей: 22
На сайте нет зарегистрированных пользователей

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

Программа тестирования (тест) - вступительные экзамены (математика, физи...
Моделирование регулировочного участка цеха на GPSS + Пояснительная записка
Моделирование процесса поступления заявок в систему, состоящую из трёх Э...

Задача о укладке вещей в рюкзаке
Решение задачи о рюкзаке: пусть 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 19:24:41 · 0 Комментариев · 9162 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Animation (Пример...
C++ : библиотека ...
Основы Delphi. Пр...
Функции Visual Basic
Delphix Sample [И...
Реализация ЭЦП по...
Cтатьи Королевств...
Converter AMR<->W...
FormShape [Исходн...
PBFoldder
Разработка распре...
Разработка клиент...
Программа "AutoRu...
VksButton
index.php + мод ...
Delphi7 Для профе...
В.Понамарев - COM...
Cooltray
Последнее загруж...
Print Grid

Топ загрузок
Приложение Клие... 100772
Delphi 7 Enterp... 97809
Converter AMR<-... 20260
GPSS World Stud... 17014
Borland C++Buil... 14189
Borland Delphi ... 10267
Turbo Pascal fo... 7372
Калькулятор [Ис... 5972
Visual Studio 2... 5206
Microsoft SQL S... 3661
Случайные статьи
Развертывание гото...
Простой метаинтерп...
Ограничения учетно...
Функции, относящие...
Постановка задачи ...
Информация о топол...
Vavada казино
Протокол передачи ...
Все хотят писать э...
Устройства доступа...
Кто пишет тесты?
Печать
Принципы реализаци...
Процедура ShowMessage
Процедура SetAllPa...
СПОСОБЫ РАСПОЗНАВА...
Глава 5. Работа с ...
Мы часто встречаем...
Измерение времени ...
Связывание данных ...
Разметка текста шр...
Как работают поиск...
Информационные и с...
сообщения
Складирование отхо...
Статистика



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


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