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

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

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

Формулируй задачу линейного целочисленного программирования

( 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

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

Это сообщение отредактировал(а) yaja - 21.6.2005, 22:58

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

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

Типичная задача заполнения рюкзака.
Не стыдно?

Цитата

Типичная задача заполнения рюкзака.

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

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

Цитата(poor_yorik @ 22.6.2005, 14:13)

Похоже на NP-полную задачу

Так и есть.

Цитата(Guest @ 22.6.2005, 11:40)

Тут все-таки нужно ЛП или ДП.

Именно!

Цитата(yaja @ 21.6.2005, 23:57)

podval что-то я не понял, что ты имел в виду.

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

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

Цитата

Я нарисовал постановку задачи в рамках ЦЛП.

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

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

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

Цитата(poor_yorik @ 22.6.2005, 14:13)

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

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

Цитата(poor_yorik @ 22.6.2005, 14:13)

Похоже на NP-полную задачу, поэтому сработает по-моему только перебор.

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

Цитата(Kurt @ 21.6.2005, 20:59)

первую доску распилить на 4, 2, 2. А вторую на 3 и 3. (плюс остаток)

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

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

Это сообщение отредактировал(а) Alex101 - 23.6.2005, 19:46

Цитата(Alex101 @ 23.6.2005, 20:45)

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

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

Цитата(podval @ 23.6.2005, 20:01)

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

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

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

Добавлено @ 13:30

Цитата(Akina @ 22.6.2005, 21:57)

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

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

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

Код

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.

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

Цитата(poor_yorik @ 27.6.2005, 22:05)

ДАААААА я решил єту задачу Динпрогом.

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

Это сообщение отредактировал(а) yaja - 28.6.2005, 14:30

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