Навигация
Главная
Поиск
Форум
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
Создание отчето... 65436
Модуль Forms 65199
Пример работы с... 64415
ТЕХНОЛОГИИ ДОСТ... 61846
Имитационное мо... 57764
Реклама
http://banketnedorogo.ru/ заказать горку из бокалов шампанского.
Сейчас на сайте
Гостей: 8
На сайте нет зарегистрированных пользователей

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

Изменения контуров и сортировка в двумерном массиве чисел на Turbo Pasca...
Моделирование процесса передачи данных по магистрали с основным и резерв...
Обучающая и тестирующая программа по здаче экзамена ПДД на Turbo Pascal ...

Реклама



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

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
IPAddresseEdit
Философия C++. Пр...
Основы Delphi
BDEPack
Библиотека програ...
Info
Ehlib
Illusion
Trojan [Исходник ...
Просмотр коммент...
Рисование PopupMenu
ShadelLabel
Трассировка прово...
Панель Календарь
Delphi 6. Учебный...
Дарахвелидзе П., ...
Mass Photo Upload
INSTANT BOOSTER v...
Apollovcl61
Printgrid

Топ загрузок
Приложение Клие... 100470
Delphi 7 Enterp... 87056
Converter AMR<-... 20078
GPSS World Stud... 12821
Borland C++Buil... 11832
Borland Delphi ... 8603
Turbo Pascal fo... 7039
Visual Studio 2... 4999
Калькулятор [Ис... 4799
FreeSMS v1.3.1 3542
Случайные статьи
Онлайн казино. Игр...
ЗАПИСИ БЕЗ КЛЮЧЕЙ
Казино Вулкан онлайн
Реализация стека в...
• Аудит удачных и ...
Нормализаторы вычи...
по любому протоколу
Область применения...
Функция MessageDlg
Слот машины онлайн...
Раскрутка сайта в ...
Назначение и особе...
Оптимальная органи...
Hello World на tur...
Эффективное исполь...
Инициализация глоб...
Использование бито...
Atari 5200 SuperSy...
Invalid Indirect r...
10-9):Табл
Технология маркиро...
Нарисовать заданну...
Двоичные файлы Web...
Схема кодирования,...
Поверхность при по...
Статистика



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


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