Навигация
Главная
Поиск
Форум
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
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Имитационное мо... 59630
Реклама
Сейчас на сайте
Гостей: 4
На сайте нет зарегистрированных пользователей

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

Моделирование системы управления качеством производственного процесса на...
Моделирование работы участка термической обработки шестерен на GPSS + По...
Программа тестирования и обучающая программа по математике на Turbo Pasc...

Реклама



Подписывайся на 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 Комментариев · 7884 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Модифицированная ...
Swat [Исходник на...
Rotolabel
CoolControls v3.0...
PCX
База данных: Книж...
В.Понамарев - COM...
Шкрыль А. - Разра...
Эффект лампы на р...
Comdrv
Delphi 7: Для про...
Самоучитель Прогр...
Базы данных в Инт...
Работа с картотеками
Print Grid
около 291 статьи ...
Allsubmitter 4.7 ...
3D Октаэдр
CS:Source - монит...
Х. М. Дейтел, П. ...

Топ загрузок
Приложение Клие... 100515
Delphi 7 Enterp... 90501
Converter AMR<-... 20093
GPSS World Stud... 15031
Borland C++Buil... 12762
Borland Delphi ... 8973
Turbo Pascal fo... 7097
Калькулятор [Ис... 5142
Visual Studio 2... 5020
FreeSMS v1.3.1 3555
Случайные статьи
Исключения
Настройка меню “Пуск”
Вложенные таблицы
Процедура Arc - че...
Все для разработки
Классификация угро...
3.1. Принципы
групповой политики...
2.1. ЦЕЛЬ: ХРАНЕНИ...
вание цифровой под...
• Бизнес-процессы
Ограниченные типы
Просмотр списка до...
Установка нового п...
Выполнение команд,...
Площадь треугольни...
9.3. Оптимизируем ...
Что делает команда...
Работа с OLE-объек...
шифрования для фай...
Если ГВС-канал свя...
Syntax error
• Framed Protocol
Аппаратура
Форма Employee - н...
Статистика



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


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