Перебор. Задача "о раскладке по ящикам"
[SIZE="5"]Всем привет![/SIZE]
Есть задача: "Раскладка по ящикам". Имеется N предметов различного размера. Один ящик имеет строгую вместимость. Необходимо разложить все N предметов в минимальное количество ящиков.
Жадные алгоритмы или какие другие не катят(задача стоит в реализации полного перебора). Как это сделать? Нужен алгоритм. Для начала не плохо было бы понять, как получить все варианты перебором, а как выбрать наиболее оптимальный разберусь уж :)
Подскажите сначала, как риализовать перебор для одного ящика (впринцепе в этом то и вопрос).
Думается мне, надо зафиксировать один предмет, который будет всегда в ящике(начнём с первого до последнего), затем из множества предметов искать другие, которые ещё могут туда влесть (для которых в ящике ещё есть место) и зафиксировать и этот предмет (будет всегда в ящике), но только в том случае, если туда можно положить ещё предмет(если никакой другой предмет после вставки не влезит, этот не фиксируем). Как только кончились комбинации при зафиксированных предметах, разфиксируем последний и вместо него зафиксируем следующий (разумеется, если для него ещё есть место), если только по значению(размеру) он не равен уже ранее зафиксированному. И так до тех пор, пока мы уже не сможем фиксировать самый первый (т.е. все возможные комбинации, удовлетворяющие условию, перебраны). Подбирать предметы до тех пор, пока не кончатся комбинации. Таким образом можно пербрать все варианты заполнения одного ящика. Перебирать варианты будем до тех пор, пока ящик не будет заполнен под завязку (свободного места в нём совсем не осталось - NULL), либо пока не будут перебраны все комбинации. Если случится второе, то из множества возможных заполнений выбрать первое попавшееся с максимальным заполнением ящика, но тогда проблемма: если делать так, то впоследствии при заполнении ящиков других, может получиться, что элемент, уже содержащийся в ящике выгоднее было бы полижить в другой ящик. Это можно как-нить учесть?
Я вообще правильно думаю или нет? Мой алгоритм перебора эфективнее, чем тупо полный, т.к. не будут рассматриваться варианты, не удовлетворяющие условию.
Сейчас попробую вывести формулу для определения количества перебраных вариантов при наихудшем раскладе...
Есть задача: "Раскладка по ящикам". Имеется N предметов различного размера. Один ящик имеет строгую вместимость. Необходимо разложить все N предметов в минимальное количество ящиков.
Жадные алгоритмы или какие другие не катят(задача стоит в реализации полного перебора). Как это сделать? Нужен алгоритм. Для начала не плохо было бы понять, как получить все варианты перебором, а как выбрать наиболее оптимальный разберусь уж :)
Подскажите сначала, как риализовать перебор для одного ящика (впринцепе в этом то и вопрос).
Думается мне, надо зафиксировать один предмет, который будет всегда в ящике(начнём с первого до последнего), затем из множества предметов искать другие, которые ещё могут туда влесть (для которых в ящике ещё есть место) и зафиксировать и этот предмет (будет всегда в ящике), но только в том случае, если туда можно положить ещё предмет(если никакой другой предмет после вставки не влезит, этот не фиксируем). Как только кончились комбинации при зафиксированных предметах, разфиксируем последний и вместо него зафиксируем следующий (разумеется, если для него ещё есть место), если только по значению(размеру) он не равен уже ранее зафиксированному. И так до тех пор, пока мы уже не сможем фиксировать самый первый (т.е. все возможные комбинации, удовлетворяющие условию, перебраны). Подбирать предметы до тех пор, пока не кончатся комбинации. Таким образом можно пербрать все варианты заполнения одного ящика. Перебирать варианты будем до тех пор, пока ящик не будет заполнен под завязку (свободного места в нём совсем не осталось - NULL), либо пока не будут перебраны все комбинации. Если случится второе, то из множества возможных заполнений выбрать первое попавшееся с максимальным заполнением ящика, но тогда проблемма: если делать так, то впоследствии при заполнении ящиков других, может получиться, что элемент, уже содержащийся в ящике выгоднее было бы полижить в другой ящик. Это можно как-нить учесть?
Я вообще правильно думаю или нет? Мой алгоритм перебора эфективнее, чем тупо полный, т.к. не будут рассматриваться варианты, не удовлетворяющие условию.
Сейчас попробую вывести формулу для определения количества перебраных вариантов при наихудшем раскладе...
Тяжело как-то с ящиками, представляется несколько измерений, зависимость от способа укладки одних и тех же ящиков. Лучше вначале для одного измерения алгоритм придумать. Например, в ячейках памяти, или в отрезках.
Типа так (совсем упрощенно): найти наибольшую сумму для чисел 2, 3, 4, 7, которая не больше восьми.
Типа так (совсем упрощенно): найти наибольшую сумму для чисел 2, 3, 4, 7, которая не больше восьми.
Видится мне такая зацепка. Допустим, у нас есть куча предметов разного размера. Если я правильно понял условие, то ящики одинаковые. Тогда я бы отсортировал предметы по порядку и дальше можно попробовать перебором как в нижеприведённой методике.
Методика: Примем объём ящика за V, размер предмета М[1] за наименьший, М[N] за наибольший. Начнём складывать в ящик предметы начиная с наибольшего. Тогда для первого ящика имеем остаток места V` = V - M[N]. Потом перебираем предметы от n = N - 1 до 1 с тем, чтобы выявить первый предмет, такой что M[n] <= V`. Если размеры равны, берём второй ящик. Если не равны, повторяем перебор от M[n - 1] до M[1]. Пахнет рекурсией. Предметы так же можно отсортировать по убыванию размера, тут, ИМХО, дело вкуса.
Методика: Примем объём ящика за V, размер предмета М[1] за наименьший, М[N] за наибольший. Начнём складывать в ящик предметы начиная с наибольшего. Тогда для первого ящика имеем остаток места V` = V - M[N]. Потом перебираем предметы от n = N - 1 до 1 с тем, чтобы выявить первый предмет, такой что M[n] <= V`. Если размеры равны, берём второй ящик. Если не равны, повторяем перебор от M[n - 1] до M[1]. Пахнет рекурсией. Предметы так же можно отсортировать по убыванию размера, тут, ИМХО, дело вкуса.
[QUOTE=Kogrom]Тяжело как-то с ящиками, представляется несколько измерений, зависимость от способа укладки одних и тех же ящиков. Лучше вначале для одного измерения алгоритм придумать. Например, в ячейках памяти, или в отрезках.
[/QUOTE]А разве алгоритм для одномерного случая не пригодится нам, если мы будем укладывать шары, кубы или вообще мешки с водой? Ну то есть такие предметы, которые характеризуются только объёмом, который не зависит от способа укладки? По-моему, задача в таком условии дана для одномерного случая.
Хотя что-то мне вспоминается задача размещения нескольких прямоугольников внутри одного. Например, при создании проекта раскроя листа в мебельном производстве. Так что фиг его знает.
[/QUOTE]А разве алгоритм для одномерного случая не пригодится нам, если мы будем укладывать шары, кубы или вообще мешки с водой? Ну то есть такие предметы, которые характеризуются только объёмом, который не зависит от способа укладки? По-моему, задача в таком условии дана для одномерного случая.
Хотя что-то мне вспоминается задача размещения нескольких прямоугольников внутри одного. Например, при создании проекта раскроя листа в мебельном производстве. Так что фиг его знает.
Цитата: Sanila_san
Методика: Примем объём ящика за V, размер предмета М[1] за наименьший, М[N] за наибольший...
Чёт здесь пахнет чем-то большим, чем тупо перебор... Это хороший и быстрый алгоритм, но по принципу работы будет очень похож на жадный, ведь забивать в ящики он всегда будет предметы максимального размера (из тех, что вообще туда могут вместиться) до тех пор пока самый маленький не будет вмещаться... Именно...жадный алгоритм :)
А если упростить: Есть один ящик с фисированным объёмом и набор предметов. Надо забить его по максимуму... Как будет выглядить перебор для этого случая???
А предметы трёхмерные или у них считается только объём? Если только объём, тогда всё точно так же, как я описал, только что может не все предметы влезут. То есть как: берём наибольший предмет, подбираем к нему меньший так, чтобы они оба влезали в ящик, если место остаётся - перебираем ещё вплоть до самого малого, пока место не пропадёт совсем. Например, есть предметы размером от 1 до 9, и ящик размером 16. Тогда берём предметы размером 9, 7, или 9, 6, 1, ну и так далее. Тут вопрос, что важнее: количество предметов или заполнение ящика?
А если это задача набивания контейнера домашним скарбом при переезде, тогда сложнее. Хотя тоже как сложнее: надо укладывать предметы так, чтобы максимальный размер не выходил за габариты ящика, ну и чтобы размер укладки стремился к размеру ящика. Как это сделать, пока не думал, но как-то делается.
А если это задача набивания контейнера домашним скарбом при переезде, тогда сложнее. Хотя тоже как сложнее: надо укладывать предметы так, чтобы максимальный размер не выходил за габариты ящика, ну и чтобы размер укладки стремился к размеру ящика. Как это сделать, пока не думал, но как-то делается.
Цитата: Sanila_san
берём наибольший предмет, подбираем к нему меньший...
И получим не что иное, как "Жадный алгоритм" :) А мне нужен перебор... Просто никак не могу понять как програмно перебрать все варианты заполненности одного ящика по максимуму.
У предмета есть только объём, у ящика только вместимость. Надо как можно больше затолкать в ящик. Меня сейчас интересует, как прописать код (желательно на C++) чтобы прорамма выдала все возможные наборы заполненности ящика...
Я знаю три способа реализации перебора, при решения комбинаторных задачах.
backtracking, метод ветвей и границ, динамическое программирование.
Полный перебор осуществляется через backtracking.
backtracking, метод ветвей и границ, динамическое программирование.
Полный перебор осуществляется через backtracking.
Цитата: DeVOLT
И получим не что иное, как "Жадный алгоритм" :) А мне нужен перебор...
Ну так перебирайте!
В общем виде идея простая - для каждого ящика построить список вещей, положенных в него (отталкивайтесь от этого).
Т.о. получаем внешний цикл - по ящикам. В нем вызываем функцию, которая может для заданного объема ящика построить список вещей.
Как можно организовать построение списка: строим все комбинации вещей и выбираем из них лучшую (оптимизация перебора - суть динамического программирования).
Предварительная оценка временной сложености где-то O(log N * N^2) (К количество ящиков).
Кстати, ящики наверно стоит сперва отсортировать по возрастанию и забивать сперва самые маленькие.
Я бы отсортировал ящики по убыванию. А потом через backtracking стал бы их заполнять. Наилучшее решение, будет если по максимуму загрузить ящики наибольшего объема.
Мудрое слово
Цитата: Mukhitov
backtracking
Я полагаю это, по-русски, перебор с возвратом? Как в ферзях и обходе конем шахматной доски?
Честно говоря особой проблемы "тупого" перебора не вижу. Внешний цикл по количеству предметов, внутренний цикл(ы) - по их всевозможным комбинациям. Может я неправильно понял задачу, но вроде это задача укладки рюкзака, она является NP-полной методов решения ее за полиномиальное время не существует (т.е. только полный перебор). На этой задаче базируются некоторые криптоалгоритмы. Если не прав - буду рад услышать опровержения.
Цитата: Phodopus
...внутренний цикл(ы) - по их всевозможным комбинациям.
Как это реализовать в коде? Просто куча вложенных циклов? т.е если в ящик пихать до 3-х предметов, соответственно 3 цикла и т.д.? А можно без нагромождения циклов? Может рекурсия?
[SIZE="4"]Буду очень очень очень благодарен, если кто поделится кусочком кода)))[/SIZE]
В правильном направлении мыслите товарищ :)
Конечно с рекурсией.
Конечно с рекурсией.
Сделайте перебор классных алгоритмов и используйте как можно больше.
Сначала я понял что можно написать программу решения всех
примеров в цикле от 1 до 4 знаков +-*/ c числами заданными
вначале X2=10 X3=50 X4=-25
X-подставляеться от -50 до 100
prim=X+-*/X2+-*/X3+-*/X4
сначало пример без скобок, потом со скобками
prim=(X+-X2)+-*/(X3+-X4)
После решения всех примеров получиться массив(>20 МегаБайт) в
котором можно по индексам находить результат.[/color]
Но это еще не все дальше я понял что можно представить функции и
примеры и операторы как числа, тоесть от 1 до 5 операторы(1..4
ФУНКЦИЙ) и т.д.
1 if [c else]
2 for [c break]
3 do while [или while do]
4
switch()
{
0:; //запускаеться function1..1000000
break;
1:; // function1..1000000
break;
//..до 10
10:; // function1..1000000
//все остальные разнообразные значения которые принимала переменная
else:; //function1..1000000
break;
}
можно сделать вариант с решением всех примеров с нужными
функциями С++ и тогда можно после выполнения их всех искать в
массиве по отсартированным индексам =
(числа которые были перед кодом)
1строка пример
2строка function
3строка пример
(числа которые стали в конце)
Но намного лучше выполнить все алгоритмы в цикле до 10 вложеностей if
и 5 else и после каждой можно запускать(или хотть какую другую или
самому написать) стандартную функцию рисования
многоугольников из массива и ждите когда они все нарисуються >1
минуту или по линиям что-бы найти хорошие узоры или похожие на
введеные мышкой.
ввести переменную Cx-нажатие на клавиши и управлять алгоритмом
курсором а можно заняться набиранием алгоритма общего для всех
игр((для первых)это сложно) и добавлять в него нужные функции (по
простому для эффектов )и все будет сразу
компилироваться.
Если сделать все алгоритмы правильно то они будут все делать.
Потом запускать интересные FUNCTIONы в цикле go to.
Но вообще то на языке программирования можно сделать случайную функцию
из операторов, примеров и функций(случайных):
function randomcode(a;b;c;d;e;f)// или int abc[6]
{
// обнуление
randomPRIMER;
if(a>b){randomPRIMER;}
randomPRIMER;
randomPRIMER;
if((a>b)and(c<d)){randomPRIMER;
}else{
randomPRIMER;
}
if((a>b)and(c<d)){if((a>d)and(d==b)){randomPRIMER;
}else{
randomPRIMER;
}randomPRIMER;
}else{if((a==b)and(c<d)){randomPRIMER;
}else{
randomPRIMER;
}
randomPRIMER;
}
}
и записать сгенерированный код в файл программы '*.cpp'
или попробовать применять его для изменения чисел прямо в программе.
А в этой задаче я бы сделал так если высота и ширина(и длина) всех предметов в которые нужно положить в ящик разная то надо делать полный перебор
сложить все предметы во всех последовательностях а если в ширину они шире или выше то выйти.И можно найти все варианты размещения предметов в ящике или выйти после нахождения первого и приступить к рисованию.Вот и все.
Сначала я понял что можно написать программу решения всех
примеров в цикле от 1 до 4 знаков +-*/ c числами заданными
вначале X2=10 X3=50 X4=-25
X-подставляеться от -50 до 100
prim=X+-*/X2+-*/X3+-*/X4
сначало пример без скобок, потом со скобками
prim=(X+-X2)+-*/(X3+-X4)
После решения всех примеров получиться массив(>20 МегаБайт) в
котором можно по индексам находить результат.[/color]
Но это еще не все дальше я понял что можно представить функции и
примеры и операторы как числа, тоесть от 1 до 5 операторы(1..4
ФУНКЦИЙ) и т.д.
1 if [c else]
2 for [c break]
3 do while [или while do]
4
switch()
{
0:; //запускаеться function1..1000000
break;
1:; // function1..1000000
break;
//..до 10
10:; // function1..1000000
//все остальные разнообразные значения которые принимала переменная
else:; //function1..1000000
break;
}
можно сделать вариант с решением всех примеров с нужными
функциями С++ и тогда можно после выполнения их всех искать в
массиве по отсартированным индексам =
(числа которые были перед кодом)
1строка пример
2строка function
3строка пример
(числа которые стали в конце)
Но намного лучше выполнить все алгоритмы в цикле до 10 вложеностей if
и 5 else и после каждой можно запускать(или хотть какую другую или
самому написать) стандартную функцию рисования
многоугольников из массива и ждите когда они все нарисуються >1
минуту или по линиям что-бы найти хорошие узоры или похожие на
введеные мышкой.
ввести переменную Cx-нажатие на клавиши и управлять алгоритмом
курсором а можно заняться набиранием алгоритма общего для всех
игр((для первых)это сложно) и добавлять в него нужные функции (по
простому для эффектов )и все будет сразу
компилироваться.
Если сделать все алгоритмы правильно то они будут все делать.
Потом запускать интересные FUNCTIONы в цикле go to.
Но вообще то на языке программирования можно сделать случайную функцию
из операторов, примеров и функций(случайных):
function randomcode(a;b;c;d;e;f)// или int abc[6]
{
// обнуление
randomPRIMER;
if(a>b){randomPRIMER;}
randomPRIMER;
randomPRIMER;
if((a>b)and(c<d)){randomPRIMER;
}else{
randomPRIMER;
}
if((a>b)and(c<d)){if((a>d)and(d==b)){randomPRIMER;
}else{
randomPRIMER;
}randomPRIMER;
}else{if((a==b)and(c<d)){randomPRIMER;
}else{
randomPRIMER;
}
randomPRIMER;
}
}
и записать сгенерированный код в файл программы '*.cpp'
или попробовать применять его для изменения чисел прямо в программе.
А в этой задаче я бы сделал так если высота и ширина(и длина) всех предметов в которые нужно положить в ящик разная то надо делать полный перебор
сложить все предметы во всех последовательностях а если в ширину они шире или выше то выйти.И можно найти все варианты размещения предметов в ящике или выйти после нахождения первого и приступить к рисованию.Вот и все.