
doi: 10.15421/40290420
Наведено формалізовані постановки задач про укладання туристичного ранця, запропоновано ефективні алгоритми їх розв'язання, що загалом дало змогу отримати адекватні результати розрахунку, провести змістовний їх аналіз та вибрати вдалі постановки задач для їх подальшого застосування. З'ясовано, що процедура укладання туристичного наплічника зазвичай є проблемою як для початківців, так і бувалих мандрівників. Водночас, досвідчені туристи в таких ситуаціях володіють деякими загальними правилами, які дають їм змогу вкладати найбільш потрібні речі не тільки встановленої місткості та мінімальної ваги, але й дотримуватись деякого порядку розміщення цих речей в наплічнику і надати йому традиційну форму, що забезпечує зручність тривалого його перенесення. Виявлено, що класична постановка задачі про ранець належить до задач цілочисельного програмування, вона допускає значну кількість різних узагальнень залежно від обмежень, накладених на ранець, на предмети або на їх вибір, а також на умову отримання оптимального розв'язку задачі – булевого чи кількісного. Проаналізовано можливі варіанти її постановок, з'ясовано основні причини широкого застосування в різних областях знань. Встановлено, що задача про ранець належить до класу NP-повних задач комбінаторної оптимізації, тому для неї немає поліноміального алгоритму, здатного її розв'язати за розумний проміжок часу. Визначено особливості застосування точних методів розв'язання задачі про ранець, проаналізовано метод повного перебору можливих варіантів, метод гілок і меж, жадібний алгоритм і методи динамічного програмування. Дано рекомендації щодо вибору серед них найпридатнішого для розв'язання запропонованих у роботі постановок задач. Наведено приклади деяких практичних постановок задачі про ранець, здійснено їхню формалізацію, алгоритмізацію та програмну реалізацію, запропоновано адекватний метод розв'язання, а також проведено змістовний аналіз отриманих результатів розрахунку, на підставі яких вибрано вдалі постановки задач для їх подальшого застосування.
задача про ранець; задача цілочисельного програмування; задачі комбінаторної оптимізації; обмеження та умови задачі; умова оптимального розв'язку задачі, Forestry, SD1-669.5
задача про ранець; задача цілочисельного програмування; задачі комбінаторної оптимізації; обмеження та умови задачі; умова оптимального розв'язку задачі, Forestry, SD1-669.5
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
