Методи за решаване на проблема с раницата
Министерство на образованието и науката на Руската федерация. Държавна образователна институция за висше професионално образование "Вятски държавен хуманитарен университет"
Катедра по приложна математика и информатика
Методи за решаване на проблема с раницата
Изпълнено от студент 3-та година от групата PM-31
Сергей Перевощиков
Научен ръководител: д-р, доцент на катедрата
приложна математика и информатика
Разова Елена Владимировна
Глава 1 Проблемът с товаренето, раницата, раницата. Изложение и NP-пълнота на проблема
1.1 Изложение на проблема с раницата
1.2 NP - пълнота на проблема
Глава 2 Методи за решаване на проблема с раницата
2.1 Класификация на методите
2.2 Динамично програмиране
2.3 Пълно търсене
2.4 Клон и обвързан метод
2.5 Алчен алгоритъм
2.6 Сравнителен анализ на методите
2.7 Модификации на задачите
Класическият проблем с раницата (товаренето) е известен от много дълго време; по-долу е неговата формализация. Нека има N различни артикула, всеки елемент има тегло wi и полезност pi, има и максимално тегло W, което може да се сложи в раницата. Необходимо е да се събере такъв набор от елементи P, така че тяхната полезност да е най-голяма, а общото тегло да не надвишава W. [6]. Разбира се, никой няма да напише програма за зареждане на раница по най-добрия начин, когато тръгва на поход или пътуване, тук всичко е твърде просто и никой не мисли за това, но има по-широки приложения.
Проблемът с товаренето (проблем с раницата) и различните му модификации се използват широко на практика в приложната математика, криптографията, икономиката, логистиката, за да се намери решение за оптимално натоварване на различни превозни средства: самолети, кораби, железопътни вагони и др.
Проблемът, който разглеждаме, е NP - пълен, тоест няма полиномиален алгоритъм за него, който да го решава за разумно време, това е проблемът. Или ние избираме бърз алгоритъм, но е известно, че той не винаги решава проблема по най-добрия начин, или ние избираме точен, който отново не е работещ за големи стойности. Има няколко модификации на задачата.
1. Всеки артикул може да бъде взет само веднъж.
2. Всеки артикул може да бъде взет колкото пъти искате.
3. Всеки елемент може да бъде взет определен брой пъти
4. Има няколко ограничения за размера на раницата.
5. Някои неща имат предимство пред други.
Целта на тази работа е да подчертае основните методи за решаване на проблема с товаренето, да класифицира и сравни тези методи.
Внедрете алгоритми за решаване на класическия проблем с раницата. Тествайте ги и ги разделете на две групи: точни и приблизителни, сравнете скоростта на решението, точността. Определете в кои случаи трябва да се използва един или друг подход за решаване на проблема.