Программа-калькулятор решения Задачи о рюкзаке 0-1 (0-1 knapsack problem) огромного размера

Задача о рюкзаке 0-1 ( 0-1 knapsack problem ) для наборов в 25 тысяч предметов и объема рюкзака до 100 триллионов.

  1. Примеры применения решений задачи о рюкзаке (ранце) . Новизна и актуальность.
  2. Минимум требований к "железу" (hardware)
  3. Лучше, чем метод динамического программирования
  4. Спецификация входных и выходных данных


Примеры применения решений задачи о рюкзаке (ранце) . Новизна и актуальность.


Рюкзак 0-1 (0-1 Knapsack Problem) - это разновидность задачи, разрешающая выбирать не более одного экземпляра каждого предмета.

В Википедии [https://ru.wikipedia.org/wiki/Задача_о_ранце] похожего метода решения нет.

Зато прочитал, что задача о рюкзаке является актуальной и достаточно востребованной с точки зрения ее приложения в реальной жизни. Задача о загрузке и её модификации часто возникают в экономике, криптографии, генетике, лингвистике и логистике для нахождения оптимального из вариантов.

Цитирую наш российский сервис о схемах погрузки ( http://www.packer3d.ru/packer3d-core ):

«К сожалению, все известные алгоритмы, решающие какую-нибудь из NP-полных задач и, в частности, задачу об упаковке, имеют экспоненциальную временную сложность, что эквивалентно полному перебору всех возможных вариантов. Это означает, что даже при небольшом количестве грузов (около 50) время работы программы, реализующей такие алгоритмы, будет измеряться годами даже при использовании современных суперкомпьютеров. Недаром в 2000 году Математический институт Клэя, входящий в состав Кембриджа, включил задачу нахождение быстрого (полиномиального) алгоритма для решения переборных задач в список из 7 задач, предложив за решение каждой из них премию в 1 млн. долларов


Минимум требований к "железу" (hardware)


Компьютер сначала не хотел заглатывать и обрабатывать такие объемы информации.

Быстрый метод точного решения задачи о рюкзаке
Рис.1        Вариант для тестирования


Тест метода точного решения задачи о рюкзаке
Рис.2        Легко убедитья в доброкачественности метода

Ввод данных: из файла (образец приложен) или генерация случайного набора предметов.

Спецификация входных и выходных данных приведена в конце статьи.

Вывод результата: на форму и в новый файл

Единственный исполняемый файл (ехе-файл) программы - меньше 500 Кб.

Программа не требовательна к ресурсам (2 Гб RAM более чем достаточно).

Время работы программы (поиска решения перебором вариантов) исчисляется десятком секунд (иногда минут).

Раздвинуть пределы теперешних ограничений не проблема.

Оформить в виде библиотеки DLL не проблема.

Я для себя ставлю знак равенства между понятиями «приложение» или «программа» и «алгоритм», так как без четкого алгоритма программу не напишешь. А быстродействие программы (среди прочих равных) говорит о преимуществах алгоритма.

Лучше, чем метод динамического программирования


Данный алгоритм, как метод нахождения точного решения (0-1 knapsack problem) «задачи о рюкзаке 0-1», конечно, использует достоинства существующих алгоритмов (динамического программирования, ветвей и границ, жадности), но выгодно отличается

  1. В отличие от Динамического Программирования, можно использовать дробные числа в весах предметов и не нужно хранить огромный массив стоимостей (хотя чуть медленнее). Правда, в этом тестовом варианте, я для весов предметов сделал тип integer. Поэтому тестируйте с целыми весами предметов;
  2. В отличие от рекурсии, не нужно перегружать память рекуррентными вызовами (программа не тормозит при больших размерностях);
  3. Память (RAM, ОЗУ) расходуется пропорционально меньшему из зол... Либо весу самого тяжелого предмета (если любой из предметов помещается в рюкзак) Либо предельному весу рюкзака, если он меньше веса отдельных предметов.
  4. Время решения (перебора) пропорционально количеству предметов в наборе, а коэффициент пропорциональности зависит от веса самого тяжелого из предметов (полиномиальное).
  5. Если исходными данными является неизменный набор предметов, то задача может решаться для двух целей (последующих действий):
    • Наиболее быстрым и менее затратным способом найти набор предметов, помещающихся в рюкзак заданного веса (но тогда, для получения (следующего ответа) набора входящих предметов для нового веса задачу нужно будет решать заново, потратить такое же время).
    • Решая задачу несколько медленнее и сохраняя лучшие варианты для всех возможных весов, на выходе можно получить возможность запрашивать готовое решение (наборы предметов) для рюкзаков с меньшей вместимостью, чем предыдущий рюкзак (в только что решаемой задаче). Это будет напоминать сбор плодов с отдельной ветви дерева. Времени будет требоваться несоизмеримо меньше (этот вариант не реализован пока, но сложностей не вижу).

Предлагаю убедиться тестированием Скачать ехе-файл для тестирования


Спецификация входных и выходных данных


Входные данные.

Текстовый файл, содержащий в каждой строке через знак табуляции:

  • N номер предмета ( целое integer ).
  • W вес предмета ( целое integer).
  • P стоимость предмета ( вещественное currency ).
Строка с нулевым номером содержит допустимый вес рюкзака M ( целое Int64 ).

Выходные данные.

Текстовый файл, содержащий в нулевой строке вес оптимального рюкзака и через знак табуляции его стоимость, а во всех остальных строках:

  • указывается 1, если предмет с номером i входит в оптимальное решение и 0, если предмет с номером i не входит в оптимальное решение.
  • N номер предмета ( целое integer ).
  • W вес предмета ( целое integer ).
  • P стоимость предмета ( вещественное currency ).


Предлагаю убедиться тестированием Скачать ехе-файл для тестирования



Автоматизация документов MS Office. orenstudent.ru Помогите найти и устранить ошибку в исходном коде программы. orenstudent.ru Skype-консультирование по программированию
Скайп-консультации
Сайт помощи студентам по программированию и информатике

Program code