|
Рубрика:
Разработка /
Изучаем «1С»
|
Facebook
Мой мир
Вконтакте
Одноклассники
Google+
|
 КИРИЛЛ ТКАЧЕНКО, инженер 1-й кат., ассистент, аспирант ФГАОУ ВО «Севастопольский государственный университет», tkachenkokirillstanislavovich@mail.ru
Разработка обработки
для решения классической задачи об укладке ранца
Для некоторой конфигурации 1С 8.3 рассматривается процесс разработки обработки. Обработка предназначена для решения классической задачи об укладке ранца при ограничениях – не более одного экземпляра каждого предмета, признаки предметов и ранца – целые положительные
Во многих областях современной человеческой деятельности приходится решать задачи, связанные с работой над конечным дискретным множеством предметов. Одной из таких задач является широко известная классическая задача обукладке ранца (в некоторых источниках – рюкзака). Достаточно прост ее так называемый целочисленный вариант 0-1, когда каждый предмет может входить в ранец не более одного раза, и признаки предметов и ранца – целые положительные [1-3]. Не используя строгих математических обозначений, эта задача может быть сформулирована следующим образом.
Осуществляется выбор некоторого подмножества из конечного счетного дискретного множества предметов. Предмет описывается условными признаками веса и ценности. Необходимо, чтобы предметы выбранного подмножества обладали наибольшей суммарной ценностью, которая не превосходит некоторой предельной вместимости ранца.
Обозначается:
- nПр – количество предметов, которое планируется разместить;
- mВмест – максимальная вместимость (максимальный вес) ранца;
- iПр – номер текущего рассматриваемого предмета;
- jВмест – номер текущей вместимости;
- Веса – массив с весами предметов;
- Ценности – массив с ценностями предметов;
- Рез – результирующий массив с номерами использованных предметов;
- ДП – двумерный массив ценностей для организации динамического программирования. Строкам соответствуют номера предметов, столбцам – ценности.
Классический алгоритм в этих обозначениях включает в себя два этапа – построение таблиц динамического программирования, а затем определение собственно решения на их основе [1-3].
Статью целиком читайте в журнале «Системный администратор», №11 за 2016 г. на страницах 47-49.
PDF-версию данного номера можно приобрести в нашем магазине.
- Knapsack problem – http://www.en.wikipedia.org/wiki/Knapsack_problem.
- Котов В.М. Информатика. Методы алгоритмизации / В.М. Котов, И.А. Волков, А.И. Лапо. – Минск: Народная асвета, 2000. – 300 с.
- Ткаченко К.С. Как уложить ранец и рюкзак? / К.С. Ткаченко. – «Потенциал»: Серия «Математика. Физика. Информатика». – Декабрь, №12, 2015, ISSN 1814-6422. – С.46-53.
Facebook
Мой мир
Вконтакте
Одноклассники
Google+
|
Разработка обработки для решения классической задачи об укладке ранца
