Алгоритм балансировки элементов
А жадный алгоритм не пройдёт?
Сорри, я в названиях алгоритмов не очень 
вкратце суть можешь?
вкратце суть можешь?Сообщение удалил
Сначала - определяем, какой вес (примерно) должен быть у группы.Как у тебя алгоритм учитывает, что
Строим первую группу - берём самый большой элемент, затем - самый большой из оставшихся, чтобы не перешагнуть за границу веса группы, и т.д. - пока не подойдём к весу группы.
Точно так же выделяем вторую группу и т.д.
По идее, с каждой следующей группой всё будет легче, потому что будут уменьшаться размеры элементов...
Необходимо разделить их на группы (с заданным количеством элементов внутри группы)
whoops
Если я правильно понял тебя, в этом случае проблема будет в сильно разном количестве элементов в группе. А надо одинаковое.
Предполагается, что надо разделить на группы одинакового размера, или размеры даны для каждой группы?
Все, вопрос закрыт, всем спасибо. Придумал обходной маневр 
В предположении, что делим камешки на группы одинакового размера, неплохие результаты дает такой алгоритм:
1. Сортируем массив по убыванию
2. Начинаем прямой ход "челночка": кладем в 1 группу, во 2 группу, ..., в n-ю группу.
3. Начинаем обратный ход: кладем в n-ю группу, в n-1-ю группу, ... в 1-ю группу.
повторяем 2, 3 пока не кончатся камешки.
1. Сортируем массив по убыванию
2. Начинаем прямой ход "челночка": кладем в 1 группу, во 2 группу, ..., в n-ю группу.
3. Начинаем обратный ход: кладем в n-ю группу, в n-1-ю группу, ... в 1-ю группу.
повторяем 2, 3 пока не кончатся камешки.
Хм, да, забавно, спасибо
этот алгоритм даже на таком сломается
10, 4, 4, 4, 4, 4, 4, 1, 1
10, 4, 4, 4, 4, 4, 4, 1, 1
Все тут распинаются, а ведь постановка задачи вообще отсутствует.
Например, что значит вот это:
Сходу приходит в голову 2 варианта:
-- минимальная разность весов наибольшей и наименьшей группы (решение почти всегда очень неоднозначное)
-- минимальное среднеквадратичное отклонение от среднеарифметической массы в группе
и много чего еще можно понапридумать
Например, что значит вот это:
чтобы полученные суммарные веса групп были примерно равны?
Сходу приходит в голову 2 варианта:
-- минимальная разность весов наибольшей и наименьшей группы (решение почти всегда очень неоднозначное)
-- минимальное среднеквадратичное отклонение от среднеарифметической массы в группе
и много чего еще можно понапридумать
Улучшим характеристики алгоритма:
1. Сортируем массив весов по убыванию
2. Раскладываем n самых тяжелых камней в n групп.
3. Берем следующие n камней и кладем по принципу - самый тяжелый камень в самую легкую группу.
4. и.т.д.
1. Сортируем массив весов по убыванию
2. Раскладываем n самых тяжелых камней в n групп.
3. Берем следующие n камней и кладем по принципу - самый тяжелый камень в самую легкую группу.
4. и.т.д.
Если я верно понял автора темы, ему нужен не "самый лучший", а "хороший" вариант деления камней по группам. Так что в целом пофигу то, что именно мы минимизируем (результаты будут тоже различаться не радикально).
И еще я не понял в чем разница между
И еще я не понял в чем разница между
-- минимальная разность весов наибольшей и наименьшей группыи
-- минимальная величина максимальной разности масс двух групп
Сходу приходит в голову 3 вариантаЕсть шанс, что во всех трех вариантах задача NP-полна. Уж лучше оставить формулировку как есть
вы правы нет никакой разницы
я тупил немного
я тупил немного
Уж лучше оставить формулировку как естьа как "есть"?
какой сейчас критерий правильности решения?
может раскидать как-нибудь, и будем считать, что все ок?
Так, спокойно, давайте раскидаем "как-нибудь"
Есть шанс, что во всех трех вариантах задача NP-полна.В смысле нет гарантировано правильного решения за полиномиальное время?
Сильно в этом сомневаюсь.
В любом случае задача либо поставлена либо нет. В первом посте она не поставлена.
а как "есть"?Ну вот такая исследовательская задача...
Если я верно понял автора темы, ему нужен не "самый лучший", а "хороший" вариант деления камней по группам.А какой "хороший"?
Где критерий "хорошести"?
Как я отличу "хороший" от "нехорошего"?
Как я отличу "хороший" от "нехорошего"?у меня спросишь
Считай что он совсем хороший, если он хороший по обоим твоим критериям.
Просто хороший - если по одному из.
И плохой - если ни по одному из.
Просто хороший - если по одному из.
И плохой - если ни по одному из.
По моим сведениям, NP-полна даже следующая задача:
Есть n камней, и заданы их веса. Разбить их на две кучи таким образом, чтобы разность весов куч была минимальной.
Уж тем более, на несколько куч.
Есть n камней, и заданы их веса. Разбить их на две кучи таким образом, чтобы разность весов куч была минимальной.
Уж тем более, на несколько куч.
По моим сведениям, NP-полна даже следующая задача:хз, насчет такой задачи, думать надо
Есть n камней, и заданы их веса. Разбить их на две кучи таким образом, чтобы разность весов куч была минимальной.
Уж тем более, на несколько куч.
но в этой задаче очень существенное отличие - все кучи с одинаковым количеством камней
может это конечно мало что дает, а может и много, тоже надо думать
перебор конечно сверхполиномиальный, но может есть что-то получше перебора, хз
при двух кучах это получается одна из задач о рюкзаке - делаем рюкзак ровно в половину суммы весов и максимально полно набиваем.
ну конечно тут стоимостей нет никаких
ну конечно тут стоимостей нет никаких
при двух кучах это получается одна из задач о рюкзаке - делаем рюкзак ровно в половину суммы весов и максимально полно набиваем.вы правы задача с двумя кучами, в которых произвольное количество камней (а не одинаковое, как у автора первого поста) сводиться к задаче о рюкзаке.
ну конечно тут стоимостей нет никаких
вот только стоимости разумеется есть
(иначе задача не сведется к задаче о рюкзаке)стоимости просто равны массам. (ведь именно суммарную массу в рюкзаке мы должны максимизировать при ограничении оной в половину массы всех камней)
Тогда задача в точности как частный случай общей задачи о рюкзаке с произвольными стоимостями.
Кстати разве нет решения задачи о рюкзаке за полиномиальное время?
если P != NP, то нет, но зато есть псевдополиномиальное решение.
Кто ботал тигры на 5-м курсе ВМиК, тот знает, что это задача о наполнении контейнеров, которая NP-полна. Так что единственный способ решить эту задачу за полиномиальное время - доказать, что P=NP. Дерзайте !
--------------------------------------------------------------------------------
Есть шанс, что во всех трех вариантах задача NP-полна.
--------------------------------------------------------------------------------
В смысле нет гарантировано правильного решения за полиномиальное время?
Сильно в этом сомневаюсь.
В любом случае задача либо поставлена либо нет. В первом посте она не поставлена.
Что такое "псевдополиномиальное решение"? Каково его время выполнения?
В теории это все красиво и формально вводится, но на пальцах - сложность псевдополиномиального алгоритма полиномиально зависит от числового параметра задачи (объема рюкзака а сложность полиномиального зависела бы полиномиально только от количества параметров (например, весов предметов).
Вот тут и далее тут достаточно понятно написано как раз про это.
Вот тут и далее тут достаточно понятно написано как раз про это.
а сложность полиномиального зависела бы полиномиально только от количества параметров (например, весов предметов).насколько я понимаю речь о зависимости от суммарного размера параметров (размера входных данных)
в общем все ясно нет известного полиномиального алгоритма, значит нет.
Кто ботал тигры на 5-м курсе ВМиК, тот знает, что это задача о наполнении контейнеров, которая NP-полна. Так что единственный способ решить эту задачу за полиномиальное время - доказать, что P=NP. Дерзайте !Ты пропустил момент о том, что кучки состоят из одинакового количества элементов, а в задаче о контейнерах этого не требовалось. Хотя это ограничение может и не повлиять на сложность, но задача немного другая.
Да, не заметил..
Оставить комментарий
skvoria
Есть заданное количество элементов с определенными весами (например, 1, 1, 1, 2, 2, 3, 7, 7, 10). Необходимо разделить их на группы (с заданным количеством элементов внутри группы) таким образом, чтобы полученные суммарные веса групп были примерно равны. В данном случае, это будут10, 1, 1
7, 1, 3
7, 2, 2
Есть ли какой-нибудь правильный алгоритм для таких вещей?