Помогите разобраться к какому классу относиться задача и куда смотреть.

Есть несколько «рюкзаков» (3) есть несколько грузов с разным весом (~10).
Нужно распределить все эти грузы по рюкзакам, так, чтобы вес в каждом был минимальный.

Эммм... упс.
Прошу прощения, с оупен айди запутался

Если ничего не класть в каждый, то будет минимальный. Если же нужен хоть один, то жадный алгоритм: сортируем грузы по убыванию и берём самые лёгкие по одному в рюкзак.

Здравствуйте, Аноним, Вы писали:

А>Если ничего не класть в каждый, то будет минимальный. Если же нужен хоть один, то жадный алгоритм: сортируем грузы по убыванию и берём самые лёгкие по одному в рюкзак.

Не выйдет, если у нас один груз в 10 кг и 20 — по килограмму. Это NP-задача, или подбирать эвристику под ожидаемое распределение масс, или сразу опуститься до полного перебора, благо вариантов (относительно) немного.

Здравствуйте, http://thomethings.blogspot.com/, Вы писали:

HTB>Помогите разобраться к какому классу относиться задача и куда смотреть.

HTB>Есть несколько «рюкзаков» (3) есть несколько грузов с разным весом (~10).
HTB>Нужно распределить все эти грузы по рюкзакам, так, чтобы вес в каждом был минимальный.

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

можно исходить из такой эвристики: сортируем по убыванию веса, и по одному кладем в рюкзаки: каждый очередной груз в тот рюкзак, который меньше по весу на данный момент. Можно дополнить условием вмещаемости.
потом можно применять двух-, трех- предметные обмены: берем 2 предмета из разных рюкзаков, и пытаемся выравнить обменом веса рюкзаков (также и для 3-х предметов, ...)

Здравствуйте, http://thomethings.blogspot.com/, Вы писали:

HTB>Помогите разобраться к какому классу относиться задача и куда смотреть.

HTB>Есть несколько «рюкзаков» (3) есть несколько грузов с разным весом (~10).
HTB>Нужно распределить все эти грузы по рюкзакам, так, чтобы вес в каждом был минимальный.


задача называется линейный раскрой ( 1D, одномерный)
смысл разложить в что то в минимальное число кучек
что бы вес ( длина, ... ) не превышали некоторой величины
если емкость рюкзаков одинакова,
то задача не является NP полной
есть бесплатные программы которые это делают

Здравствуйте, http://thomethings.blogspot.com/, Вы писали:

HTB>Помогите разобраться к какому классу относиться задача и куда смотреть.

HTB>Есть несколько «рюкзаков» (3) есть несколько грузов с разным весом (~10).
HTB>Нужно распределить все эти грузы по рюкзакам, так, чтобы вес в каждом был минимальный.

Частный случай этой задачи (когда груз возможно распределить ровно) является сильно NP-полной(т.е. не существует псевдополимиальных алгоритмов).
http://en.wikipedia.org/wiki/3-partition_problem

Отсюда можно предположить, что для точного ответа потребуется перебрать все варианты. Учитывая что их всего 60000 (3^10), пока не вижу смысла копать глубже.

А>Частный случай этой задачи (когда груз возможно распределить ровно) является сильно NP-полной(т.е. не существует псевдополимиальных алгоритмов).
А>http://en.wikipedia.org/wiki/3-partition_problem

Я ошибся. Это не эквивалентные задачи! (в 3-partition_problem тройки а не три множества)

А>Частный случай этой задачи (когда груз возможно распределить ровно) является сильно NP-полной(т.е. не существует псевдополимиальных алгоритмов).
А>http://en.wikipedia.org/wiki/3-partition_problem

А>Отсюда можно предположить, что для точного ответа потребуется перебрать все варианты. Учитывая что их всего 60000 (3^10), пока не вижу смысла копать глубже.


Рассматриваю частный случай чтобы понять как с этим работать

Здравствуйте, E3E6, Вы писали:

А>>Частный случай этой задачи (когда груз возможно распределить ровно) является сильно NP-полной(т.е. не существует псевдополимиальных алгоритмов).
А>>http://en.wikipedia.org/wiki/3-partition_problem

А>>Отсюда можно предположить, что для точного ответа потребуется перебрать все варианты. Учитывая что их всего 60000 (3^10), пока не вижу смысла копать глубже.


EE>Рассматриваю частный случай чтобы понять как с этим работать

если у выс разовая задача
и ее не надо никуда встраивать
наберите поиск в яндексе
линейный раскрой + скачать
и решите свои проблемы

Здравствуйте, http://thomethings.blogspot.com/, Вы писали:

HTB>Помогите разобраться к какому классу относиться задача и куда смотреть.

HTB>Есть несколько «рюкзаков» (3) есть несколько грузов с разным весом (~10).
HTB>Нужно распределить все эти грузы по рюкзакам, так, чтобы вес в каждом был минимальный.

IMHO, Задача из области линейного программирования

Здравствуйте, http://thomethings.blogspot.com/, Вы писали:

HTB>Помогите разобраться к какому классу относиться задача и куда смотреть.

HTB>Есть несколько «рюкзаков» (3) есть несколько грузов с разным весом (~10).
HTB>Нужно распределить все эти грузы по рюкзакам, так, чтобы вес в каждом был минимальный.

[4 килобайта матов пропущено]
Не, я все понимаю, но почему эти охломоны предлагают решать задачу упаковки начиная с МЕНЬШЕГО веса?!

Здравствуйте, http://thomethings.blogspot.com/, Вы писали:

HTB>Нужно распределить все эти грузы по рюкзакам, так, чтобы вес в каждом был минимальный.

Для начала не помешал бы критерий минимальности.

Что минимальнее, 5 10 15 или 1 14 15 или 7 12 13? Я вот по твоему условию не могу ответить на этот вопрос.

Здравствуйте, Sealcon190, Вы писали:

S>Здравствуйте, http://thomethings.blogspot.com/, Вы писали:

HTB>>Нужно распределить все эти грузы по рюкзакам, так, чтобы вес в каждом был минимальный.

S>Для начала не помешал бы критерий минимальности.

S>Что минимальнее, 5 10 15 или 1 14 15 или 7 12 13? Я вот по твоему условию не могу ответить на этот вопрос.

Минимальный суммарный вес в каждом рюкзаке. Т. е. нужно равномерно раскидать весь груз по рюкзакам.

Сторонние программы не подходят.

EE>Минимальный суммарный вес в каждом рюкзаке. Т. е. нужно равномерно раскидать весь груз по рюкзакам.
EE>Сторонние программы не подходят.

Вроде всё выяснили уже? Ну про раскрой и т.д.
Partition Problem, NP полная задача с существующими псевдополиномиальными алгоритмами.
Существует в двух ипостасях. В виде проблемы точного существования разбиения множества на равные части и оптимизационной задачи (как раз ваша). Иногда ещё под Partition Problem имеется ввиду разделение на две части.

Все решения мгновенно гуглятся.
например:
http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45.HTM

Здравствуйте, Аноним, Вы писали:

EE>>Минимальный суммарный вес в каждом рюкзаке. Т. е. нужно равномерно раскидать весь груз по рюкзакам.
EE>>Сторонние программы не подходят.

А>Вроде всё выяснили уже? Ну про раскрой и т.д.
А>Partition Problem, NP полная задача с существующими псевдополиномиальными алгоритмами.
А>Существует в двух ипостасях. В виде проблемы точного существования разбиения множества на равные части и оптимизационной задачи (как раз ваша). Иногда ещё под Partition Problem имеется ввиду разделение на две части.

А>Все решения мгновенно гуглятся.
А>например:
А>http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45.HTM

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

А>>Все решения мгновенно гуглятся.
А>>например:
А>>http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45.HTM

EE>Не знал как это по-английски называется, а, на русском, ничего полезного не нагугливалось. Спасибо, буду разбираться.

Если честно, я немного запутался, потому что помимо Partition Problem есть ещё Linear Partition Problem, что несколько другое (и по моей ссылке под названием Partition Problem оно и попалось). А заодно, есть ещё задача http://en.wikipedia.org/wiki/Multiprocessor_scheduling, которая на первый взгляд, тоже самое, что и оптимизационная Partition Problem в общем случае. Вот судя по всему, последняя ссылка — это и есть нужная задача! (Это же утверждение есть и в http://en.wikipedia.org/wiki/Bin_packing_problem : If the number of bins is to be fixed or constrained, and the size of the bins is to be minimised, that is a different problem which is equivalent to the Multiprocessor scheduling problem)

В книжке Гэри, Джонсон — "Вычислительные машины и труднорешаемые задачи", написано что мультипроцессорное расписание имеет псевдополиномиальное решение (при фиксированном числе процессоров). В этой же книжке "задача разбиения" упоминается только для случая m = 2 и n=3m.

Здравствуйте, Аноним, Вы писали:

А>>>Все решения мгновенно гуглятся.
А>>>например:
А>>>http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45.HTM

EE>>Не знал как это по-английски называется, а, на русском, ничего полезного не нагугливалось. Спасибо, буду разбираться.

А>Если честно, я немного запутался, потому что помимо Partition Problem есть ещё Linear Partition Problem, что несколько другое (и по моей ссылке под названием Partition Problem оно и попалось). А заодно, есть ещё задача http://en.wikipedia.org/wiki/Multiprocessor_scheduling, которая на первый взгляд, тоже самое, что и оптимизационная Partition Problem в общем случае. Вот судя по всему, последняя ссылка — это и есть нужная задача! (Это же утверждение есть и в http://en.wikipedia.org/wiki/Bin_packing_problem : If the number of bins is to be fixed or constrained, and the size of the bins is to be minimised, that is a different problem which is equivalent to the Multiprocessor scheduling problem)

А>В книжке Гэри, Джонсон — "Вычислительные машины и труднорешаемые задачи", написано что мультипроцессорное расписание имеет псевдополиномиальное решение (при фиксированном числе процессоров). В этой же книжке "задача разбиения" упоминается только для случая m = 2 и n=3m.

О! Спасибо. Крутая книга – так доступно написана.