Задача о рюкзаке.

[Someone]

Имеются несколько "рюкзаков" заданной вместимости (возможно, разной) и "куча" предметов разного объёма, которые нужно упаковать в эти рюкзаки. Предметы делятся на две категории: те, которые обязательно надо упаковать (для них места в рюкзаках должно хватить), и те, которые упаковываются при наличии достаточного места в рюкзаке. Есть одна особенность: если одинаковые предметы попадают в один рюкзак, то они вместе занимают меньше места, чем их суммарный объём. Задача состоит в максимизации количества упакованных предметов.

Нужна литература, в которой описаны алгоритмы решения такой задачи, отличные от полного перебора, пусть даже приближённые. Я в курсе, что задача NP-полная.

P. S. Задача связана с оптимизацией производства. Программированием буду заниматься не я, меня просто спросили о методах решения.

[upgrade]

Someone в сообщении #1558698 писал(а):

Нужна литература, в которой описаны алгоритмы решения такой задачи

В гуле находит

"Задача укладки рюкзака очень сложна. Если перебирать всевозможные подмножества данного набора из k предметов, то получится решение сложности не менее чем O($2^k$ ). В настоящее время неизвестен (и, скорее всего, вообще не существует) алгоритм решения этой задачи, сложность которого является многочленом от k."

[Someone]

upgrade, я в курсе. Я же и спрашиваю о методах, которые эффективнее полного перебора, пусть даже они не дают точного решения. Важно за приемлемое время получить достаточно хорошее решение.

[eugensk]

Someone в сообщении #1558698 писал(а):

если одинаковые предметы попадают в один рюкзак, то они вместе занимают меньше места

Это может быть про нелинейный рюкзак? https://hochbaum.ieor.berkeley.edu/html ... apsack.pdf
или вот, https://www.sciencedirect.com/science/a ... 0306014500
По крайней мере, я попытался ответить, на троечку :)

[Dmitriy40]

Someone
Не так давно у нас была похожая тема: «Перераспределить кучу на кучки с min дисперсией»
Там не совсем рюкзак, но кажется как раз планирование производства. Без литературы, но вроде человек получил вполне приемлемое решение. Можно оттуда взять идеи/методы, условия же придётся уточнить под свою задачу.

[Sender]

По-моему, условие нелинейной впихиваемости одинаковых предметов можно свести к рассмотрению задачи multiple-choice knapsack problem. Т.е. если есть 2 предмета объёмом по $v_1$, при упаковке в один рюкзак дающих объём $v_2$, мы можем рассмотреть набор из 3-х предметов объёмами $v_1,v_1,v_2$ стоимостью $1,1,2$ соответственно, из которых мы можем выбрать только один.

[Sender]

Стоп, бред написал. Они ведь могут в разные рюкзаки попасть.

[Someone]

eugensk в сообщении #1558711 писал(а):

Это может быть про нелинейный рюкзак?

Похоже.

Dmitriy40 в сообщении #1558716 писал(а):

Не так давно у нас была похожая тема

Надо обдумать.

Sender в сообщении #1558800 писал(а):

Стоп, бред написал.

Не страшно. Я иногда тоже бред изрекаю.

Однако, может быть, кто-нибудь порекомендует литературу (лучше, но не обязательно на русском языке) с описаниями алгоритмов?

[Sender]

Один из возможных общих подходов к решению - переформулировать задачу в виде SMT или даже SAT, после чего натравить соответствующий специализированный решатель. У SMT более богатый язык, позволяющий компактно сформулировать задачу, в то время как SAT-решатели способны решать очень большие и/или сложные задачи. SMT- и SAT-решатели развиваются уже не первый год и позволяют решать в том числе задачи промышленной сложности. Среди этих решателей проводятся ежегодные состязания(http://www.satcompetition.org/,https://smt-comp.github.io/2021/results.html), их результаты и по большей части исходные коды программ-участников находятся в открытом доступе.

-- Чт июн 30, 2022 00:09:40 --

Но лучше, наверное, начать с динамического программирования(в данном случае это метод решения задач дискретной оптимизации, а не написание кода). С его принципами можно ознакомиться, например, в 15 главе классической книги по алгоритмам: Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн - Алгоритмы. Построение и анализ.

[пианист]

Someone
Перебор плох из-за недостаточности ресурсов или в силу сложности реализации, сиречь написания читаемого кода?
И ещё вопрос, число рюкзаков штучное или статистическое?

[Someone]

пианист в сообщении #1558875 писал(а):

Перебор плох из-за недостаточности ресурсов или в силу сложности реализации, сиречь написания читаемого кода?

Насколько я знаю, пока не пробовали. На всякий случай хорошо было бы иметь и другие методы.

пианист в сообщении #1558875 писал(а):

И ещё вопрос, число рюкзаков штучное или статистическое?

Фиксированное количество (то ли $5$, то ли $6$, мне точно не сказали).

Содержательно "рюкзаки" — это рабочие, занимающиеся сборкой, которых надо загрузить работой достаточно равномерно. Попутно есть надежда, что это позволит увеличить объём производства. На практике часто получается так, что один уже свою работу сделал и сидит без дела, а зарплата у них одинаковая. Поэтому занятые ему завидуют. Там есть какие-то технологические ограничения, которые не позволяют загрузить "бездельника" работой, пока остальные не закончат. Составить распределение заданий раз и навсегда нельзя, потому что набор устройств, которые они собирают, постоянно меняется.

Sender в сообщении #1558863 писал(а):

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

Надо будет попробовать.

[Geen]

Someone в сообщении #1558898 писал(а):

не позволяют загрузить "бездельника" работой, пока остальные не закончат

Но это же уже не упаковка рюкзаков?...

[Someone]

Geen в сообщении #1558904 писал(а):

Но это же уже не упаковка рюкзаков?

Почему? Просто не осталось предметов такого объёма, который мог бы влезть. В любом случае, весьма похоже.

[Sender]

Someone в сообщении #1558898 писал(а):

Содержательно "рюкзаки" — это рабочие, занимающиеся сборкой, которых надо загрузить работой достаточно равномерно.

Может, тогда имеет смысл максимизировать не число предметов, а минимальную загрузку рюкзака?

[Someone]

Sender в сообщении #1558907 писал(а):

Может…

Пусть подумают, что лучше. Мне задача была сформулирована так, что я её понял как написано в первом сообщении, и со мной согласились. Меня просили порекомендовать методы решения. До полного перебора они сами додумались, но пока не реализовали.