МОСКОВСЬКИЙ АВІАЦІЙНИЙ ІНСТИТУТ
(Національний дослідницький університет)
Звіт
по курсовій роботі за курс:
"Теорія оптимального планування та Управління"
Тема
"Задача про ранці"
Москва 2012
Зміст
1. Постановка завдання
2. Метод рішення
3. Загальний опис програмного модуля
4. Алгоритм методу
5. Визначення даних
6. Вхідний файл
7. Вихідний файл
8. Тестова перевірка
9. Лістинг програми
Висновки
1. Постановка завдання
Задача про ранці.
Алгоритм неявного лексикографічного перебору.
Розробити структуру даних, реалізацію алгоритму з її використанням та програмну реалізацію.
Провести тестову перевірку.
2. Метод рішення
Дається набір з N предметів. Нехай MaxW - обсяг рюкзака, Pi - вартість i-го предмета, Wi - вага i-го предмета. Value [W, i] - максимальна сума, яку треба знайти. p align="justify"> На кожному кроці за вагою 1
Якщо ми вже знайшли Value [1. W, 1. i-1], тобто для ваги менше або рівного W і з предметами, взятими з 1. N-1. p align="justify"> Розглянемо предмет N, якщо його вага WN менше W перевіримо чи варто його брати.
Якщо ми його беремо, то вага стає W-Wi, тоді Value [W, i] = Value [W - Wi, i-1] + Pi (для Value [W - Wi, i- 1]) рішення вже знайдено залишається тільки додати Pi.
Якщо його не брати то вага залишиться тим же і Value [W, i] = Value [W - Wi, i-1].
З двох варіантів вибирається той, який дає найбільший результат.
лістинг програма алгоритм
3. Загальний опис програмного модуля
3.1 Призначення модуля.
Модуль призначений для вирішення завдання про ранці.
.2 Обмеження.
При роботі з модулем для коректної роботи програми потрібно, щоб вхідний файл знаходився в каталозі, з якого був викликаний виконуваний модуль.
Якщо файл не буде знайдений або містить некоректні дані, то завантаження не буде зроблена.
.3 Мова програмування.
Програма написана на мові програмування Delphi7
