Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Распилить доски на куски?..


Автор: Kurt 21.6.2005, 20:59
Допустим, есть n-ое (n - может быть большим, скажем, около 1000) количество одинаковых по длинне досок.
Далее есть последовательность длин мелких досок, к-е нужно получить из больших. Нужно найти такое правило распила для каждой из больших досок, чтобы остаток, мусор, обрубки от распила были минимизированны.
Ну, для примера, задачу можно сформулировать так:
есть две большие доски по 8 метров каждая.
есть такая последовательность кусочков, к-е нужно получить:
4, 2, 3, 2, 3 (заметим, что длины могут повторяться!).
Решением этой задачи будет такой распил:
первую доску распилить на 4, 2, 2.
А вторую на 3 и 3. (плюс остаток)

Может, есть готовые решения?

З.Ы. Задачка не является заданием в школу, университет и т.п...

Автор: podval 21.6.2005, 21:32
Формулируй задачу линейного целочисленного программирования

( SUMi (Li) - SUMi SUMj ( Kij*lj ) ) -> min,

или учитывая, что все Li = L

( n*L - SUMi SUMj ( Kij*lj ) ) -> min,

где n - количество досок, L - их длина,
Kij - количество заготовок j-го типа в i-й доске - понятно, что это матрица?
lj - длина заготовки j-го типа,
SUMi - сумма по i,
SUMj - сумма по j,

с ограничениями:

SUMi (Kij) <= Mj - для всех j - ограничение на количество заготовок каждого типа,

SUMj (Kij*lj) <= Li - для всех i - это ограничение вводится, чтобы не вылетать за границу отдельной доски.

Осталось правильно раскидать значения длин заготовок по таблице (матрице) Kij smile

Автор: yaja 21.6.2005, 22:57
podval
что-то я не понял, что ты имел в виду. можешь расписать поподробнее pls smile
имхо, задачу можно решать жадным алгоритмом. т.е. отсортируем доски по длинне и начнем их пилить на куски с минимальным остатком, начиная с самой большой доски. Кажись всегда остаток будет минимизирован smile

Автор: Kurt 21.6.2005, 23:15
yaja
Собственно, это первый вариант, что пришел мне в голову..

Автор: Guest 22.6.2005, 10:40
yaja
Не так все очевидно.
Если на доску максим. размера влазит не больше одной макс. заготовки, то так и будет.
А если на доску влазит 2-3 макс. заготовки? Как лучше: выпилить из доски например, 2 макс. заготовки, а из остатка - более мелкие, или: из каждой доски выпиливать только по одной максимальной, а из остатков - мелкие. Тут все-таки нужно ЛП или ДП.
Интересная задача.
Я когда ремонт делал, тоже пытался по-научному подойти. Да на глаз оказалось быстрее smile

Автор: Akina 22.6.2005, 11:31
Типичная задача заполнения рюкзака.
Не стыдно?

Автор: yaja 22.6.2005, 12:42
Цитата
Типичная задача заполнения рюкзака.

Ну да, типичная smile, но все-таки как она решается?
Меня смущает то, что рюкзаков(досок) сдесь много smile

Автор: poor_yorik 22.6.2005, 13:13
Akina тут как раз задача рюкзака не подходит, это ближе к задаче о камнях и двух кучах, но тоже не то.
Получается, чтобы хранить остатки на каждой доске как в задаче с рюкзаком, мы еще и должны хранить, какую доску из какой большой мы спилили, а это занимает очень много памяти. smile
Похоже на NP-полную задачу, поэтому сработает по-моему только перебор.

Автор: podval 22.6.2005, 19:23
Цитата(poor_yorik @ 22.6.2005, 14:13)
Похоже на NP-полную задачу

Так и есть.

Цитата(Guest @ 22.6.2005, 11:40)
Тут все-таки нужно ЛП или ДП.

Именно!


Цитата(yaja @ 21.6.2005, 23:57)
podval
что-то я не понял, что ты имел в виду.

Я нарисовал постановку задачи в рамках ЦЛП.
Только немного коряво, торопился. Я поправил свой первый пост.

Автор: yaja 22.6.2005, 20:41
Вопрос немного не в тему. Я правильно понимаю ЛП - линейное программирование. ДН - динамическое программирование.
Добавлено @ 20:46
Вопрос немного не в тему. Я правильно понимаю ЛП - линейное программирование. ДН - динамическое программирование.
Имхо совсем не очевидно, что эта задача np-полная, а если это так, то как это объяснить?
Цитата
Я нарисовал постановку задачи в рамках ЦЛП.

Понял smile только странно, что я не сразу это сделал. Эх, надо вдумчивей читать smile

Автор: Akina 22.6.2005, 21:57
poor_yorik
Замени доску определенной длины на рюкзак определенного объема, длины кусков на объем упаковываемых предметов - и перед тобой задача о рюкзаке.

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

Цитата(poor_yorik @ 22.6.2005, 14:13)
чтобы хранить остатки на каждой доске как в задаче с рюкзаком, мы еще и должны хранить, какую доску из какой большой мы спилили, а это занимает очень много памяти.

классическое решение НЕ ТРЕБУЕТ хранения остатков. Хотя бы потому что первый шаг решения - сортировка рюкзаков и предметов по размеру (по отдельности есссно)...

Цитата(poor_yorik @ 22.6.2005, 14:13)
Похоже на NP-полную задачу, поэтому сработает по-моему только перебор.

Мало того что она НЕ NP-полная, так она еще и решается ЗА ОДИН ПРОХОД.

Автор: Alex101 23.6.2005, 19:45
Цитата(Kurt @ 21.6.2005, 20:59)
первую доску распилить на 4, 2, 2.
А вторую на 3 и 3. (плюс остаток)

Немного непонятны требования.
Почему будет считаться хуже такое решение:
Первую на 4 и 3
Вторую на 2+2+3
?

Остаток и в твоем решении и в этом одинаковый (2).

Автор: podval 23.6.2005, 20:01
Цитата(Alex101 @ 23.6.2005, 20:45)
Остаток и в твоем решении и в этом одинаковый (2).

Нормальная ситуация. Оптимизационная задача может иметь несколько решений. А может вообще не иметь.

Автор: Alex101 24.6.2005, 13:27
Цитата(podval @ 23.6.2005, 20:01)
Нормальная ситуация. Оптимизационная задача может иметь несколько решений. А может вообще не иметь

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

Перебор, естественно, с отсечением ветвей.
Задача ведь не какой длины доски выбрать, а уколбасить в имеющиеся, чтобы кол-во оставшихся кусочков минимальным было.

Добавлено @ 13:30
Цитата(Akina @ 22.6.2005, 21:57)
Мало того что она НЕ NP-полная, так она еще и решается ЗА ОДИН ПРОХОД.

Любопытно было бы взглянуть на решение. Честно говоря, сильно сомневаюсь, что возможно, но вдруг удивлюсь? smile

Автор: poor_yorik 27.6.2005, 22:05
ДАААААА я решил єту задачу Динпрогом.
Просто я не совсем так понял условие, и задача вышла намного сложнее. smile
Вот код моего решения

Код

program interest;

{$APPTYPE CONSOLE}

Var
 ans:array [0..10000] of integer;
 big,little:array [1..1000] of integer;
 W:integer;
 answer:longint;
 m,n:integer;
 i,j:integer;
begin
 writeln('Chislo bolwix dosok:');
 readln(m);
 writeln('Vesa bolwix dosok');
 W:=0;
 for i:=1 to m do begin
  read(big[i]);
  if big[i]>W then W:=big[i];
 end;
 writeln('Chislo malux dosok:');
 readln(n);
 writeln('Vesa malux dosok');
 for i:=1 to n do read(little[i]);
 for i:=1 to W do begin
  ans[i]:=i;
  for j:=1 to n do
   if (i-little[j]>=0) and (ans[i-little[j]]<ans[i])
    then ans[i]:=ans[i-little[j]];
 end;
 answer:=0;
 for i:=1 to m do
  answer:=answer+ans[big[i]];
 writeln(answer); 
end.


Я просто не посмотрел внимательно на пример...

Автор: yaja 28.6.2005, 14:29
Цитата(poor_yorik @ 27.6.2005, 22:05)
ДАААААА я решил єту задачу Динпрогом.

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

Автор: poor_yorik 1.7.2005, 11:02
Смотри yaja!
Во первых, я оттестировал свою прогу на все 100. И Для всех мерзких случаев, которые сам придумал. smile
Ты не будешь спорить, что если бы у нас была одна доска, то задача была бы почти-что такая же как задача про рюкзак. В принципе она больше похожа на задачу про камни, если ты знаешь, но с одним большим отличием: у нас количество маленьких досок одного типа, на которые мы можем рубить большие НЕОГРАНИЧЕНО. Я это сам вначале не заметил.
То есть если, у нас две большие доски длинной 5 и 7. И набор длин 2, 3, 4. То оптимальное решение [2, 3] и [3, 4]. Ответ остаток 0.
Так вот у меня задача динпрогом находит ответ (остаток) для всех досок длинами от 0 до Lmax, где Lmax - длина наибольшей из даных досок. А потом она уже сумирует остатки нужных мне досок так и получает сумарный результат. smile
Советую тебе посмотреть что-нибудь по ДинПрогу, а особенно о задаче про рюкзак.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)