Режем торт

[grizzly]

Помогли мне написать программку и я теперь вооружён для дальнейшего изучения вопроса. Буду в неспешном режиме копаться дальше.

worm2 в сообщении #1077293 писал(а):

скорее всего, решения из 14 разрезов довольно многочисленны и разнообразны

Под катом все (надеюсь) решения, у которых максимальный кусок строго меньше 60 г. (я резал только 420-граммовые торты). 69 решений. Надеюсь, что перебор полный и я ничего не пропускаю (это я ещё буду проверять).

(Решения для 7--14)

[59, 49, 45, 44, 39, 35, 35, 25, 25, 21, 16, 15, 11, 1]
[59, 55, 49, 45, 39, 35, 31, 29, 25, 21, 15, 11, 5, 1]
[59, 49, 45, 40, 39, 35, 31, 29, 25, 21, 20, 15, 11, 1]
[59, 49, 45, 39, 35, 34, 31, 29, 26, 25, 21, 15, 11, 1]
[59, 49, 44, 39, 35, 34, 31, 29, 26, 25, 21, 16, 11, 1]
[59, 54, 49, 45, 39, 35, 31, 29, 25, 21, 15, 11, 6, 1]
[59, 49, 45, 41, 39, 35, 31, 29, 25, 21, 19, 15, 11, 1]
[59, 49, 44, 41, 39, 35, 31, 29, 25, 21, 19, 16, 11, 1]
[59, 49, 41, 39, 35, 34, 31, 29, 26, 25, 21, 19, 11, 1]
[58, 57, 51, 47, 43, 37, 33, 27, 23, 17, 13, 9, 3, 2]
[58, 57, 51, 47, 41, 37, 33, 27, 23, 19, 13, 9, 3, 2]
[58, 51, 48, 47, 43, 37, 33, 27, 23, 17, 13, 12, 9, 2]
[58, 57, 48, 47, 38, 37, 33, 27, 23, 22, 13, 12, 3, 2]
[57, 51, 47, 41, 37, 33, 31, 29, 27, 23, 19, 13, 9, 3]
[57, 49, 47, 39, 37, 33, 32, 28, 27, 23, 21, 13, 11, 3]
[57, 48, 47, 38, 37, 33, 31, 29, 27, 23, 22, 13, 12, 3]
[57, 47, 39, 38, 37, 33, 31, 29, 27, 23, 22, 21, 13, 3]
[57, 47, 39, 38, 37, 33, 32, 28, 27, 23, 22, 21, 13, 3]
[57, 48, 47, 41, 37, 33, 31, 29, 27, 23, 19, 13, 12, 3]
[57, 49, 47, 42, 37, 33, 32, 28, 27, 23, 18, 13, 11, 3]
[57, 48, 47, 43, 38, 37, 33, 27, 23, 22, 17, 13, 12, 3]
[57, 47, 43, 41, 37, 33, 31, 29, 27, 23, 19, 17, 13, 3]
[57, 55, 48, 47, 43, 37, 33, 27, 23, 17, 13, 12, 5, 3]
[57, 52, 47, 45, 43, 37, 33, 27, 23, 17, 15, 13, 8, 3]
[57, 48, 47, 43, 41, 37, 33, 27, 23, 19, 17, 13, 12, 3]
[57, 47, 45, 43, 38, 37, 33, 27, 23, 22, 17, 15, 13, 3]
[57, 47, 43, 42, 37, 35, 33, 27, 25, 23, 18, 17, 13, 3]
[57, 47, 43, 39, 37, 33, 32, 28, 27, 23, 21, 17, 13, 3]
[57, 47, 43, 38, 37, 33, 31, 29, 27, 23, 22, 17, 13, 3]
[57, 47, 43, 37, 35, 33, 32, 28, 27, 25, 23, 17, 13, 3]
[55, 54, 49, 45, 39, 35, 31, 29, 25, 21, 15, 11, 6, 5]
[54, 44, 40, 39, 34, 31, 30, 30, 29, 26, 21, 20, 16, 6]
[54, 53, 51, 43, 41, 33, 31, 29, 27, 19, 17, 9, 7, 6]
[54, 53, 44, 43, 41, 39, 31, 29, 21, 19, 17, 16, 7, 6]
[53, 49, 44, 43, 41, 39, 31, 29, 21, 19, 17, 16, 11, 7]
[53, 51, 43, 41, 33, 31, 30, 30, 29, 27, 19, 17, 9, 7]
[53, 52, 43, 42, 41, 32, 31, 29, 28, 19, 18, 17, 8, 7]
[53, 52, 43, 42, 33, 32, 31, 29, 28, 27, 18, 17, 8, 7]
[53, 51, 43, 41, 33, 32, 31, 29, 28, 27, 19, 17, 9, 7]
[53, 51, 43, 41, 37, 33, 31, 29, 27, 23, 19, 17, 9, 7]
[53, 51, 43, 41, 38, 33, 32, 28, 27, 22, 19, 17, 9, 7]
[53, 43, 42, 41, 33, 32, 31, 29, 28, 27, 19, 18, 17, 7]
[53, 51, 43, 41, 38, 37, 33, 27, 23, 22, 19, 17, 9, 7]
[53, 43, 41, 37, 33, 32, 31, 29, 28, 27, 23, 19, 17, 7]
[53, 47, 43, 37, 33, 32, 31, 29, 28, 27, 23, 17, 13, 7]
[52, 49, 47, 42, 37, 33, 32, 28, 27, 23, 18, 13, 11, 8]
[52, 47, 42, 40, 38, 37, 32, 28, 23, 22, 20, 18, 13, 8]
[52, 43, 42, 40, 38, 33, 32, 28, 27, 22, 20, 18, 17, 8]
[52, 45, 43, 42, 38, 33, 32, 28, 27, 22, 18, 17, 15, 8]
[52, 49, 47, 42, 38, 37, 32, 28, 23, 22, 18, 13, 11, 8]
[52, 48, 43, 42, 41, 38, 32, 28, 22, 19, 18, 17, 12, 8]
[51, 47, 43, 41, 37, 33, 31, 29, 27, 23, 19, 17, 13, 9]
[51, 47, 41, 37, 33, 31, 30, 30, 29, 27, 23, 19, 13, 9]
[51, 43, 41, 37, 33, 31, 30, 30, 29, 27, 23, 19, 17, 9]
[51, 47, 44, 41, 37, 34, 33, 27, 26, 23, 19, 16, 13, 9]
[51, 48, 43, 41, 38, 37, 33, 27, 23, 22, 19, 17, 12, 9]
[51, 47, 41, 37, 34, 33, 31, 29, 27, 26, 23, 19, 13, 9]
[51, 44, 43, 41, 37, 33, 31, 29, 27, 23, 19, 17, 16, 9]
[51, 48, 47, 41, 37, 33, 31, 29, 27, 23, 19, 13, 12, 9]
[51, 44, 41, 39, 34, 33, 31, 29, 27, 26, 21, 19, 16, 9]
[49, 45, 44, 39, 36, 35, 34, 26, 25, 24, 21, 16, 15, 11]
[48, 47, 43, 41, 38, 37, 33, 27, 23, 22, 19, 17, 13, 12]
[48, 47, 41, 38, 37, 33, 31, 29, 27, 23, 22, 19, 13, 12]
[48, 47, 42, 40, 38, 37, 32, 28, 23, 22, 20, 18, 13, 12]
[47, 39, 38, 37, 33, 32, 31, 29, 28, 27, 23, 22, 21, 13]
[47, 43, 41, 37, 34, 33, 31, 29, 27, 26, 23, 19, 17, 13]
[47, 43, 41, 38, 37, 33, 31, 29, 27, 23, 22, 19, 17, 13]
[47, 44, 43, 41, 37, 34, 33, 27, 26, 23, 19, 17, 16, 13]
[44, 43, 41, 39, 34, 33, 31, 29, 27, 26, 21, 19, 17, 16]

Для 8--16 тот же алгоритм дал всего 3 решения, чем немало меня удивил (максимальный кусок здесь также строго меньше 105 грамм):
[103, 88, 80, 73, 68, 67, 58, 53, 52, 47, 38, 37, 32, 25, 17, 2]
[94, 80, 79, 76, 74, 64, 61, 59, 46, 44, 41, 31, 29, 26, 25, 11]
[88, 82, 80, 73, 68, 67, 58, 53, 52, 47, 38, 37, 32, 25, 23, 17] -- это уже нашёл раньше Sender

Для 9--18 решений нет. Я также не верю, что для 9--18 найдутся решения и с максимальным куском 280 грамм.

Для задачи 9--19 нужно ещё колдовать с алгоритмом. Полный перебор на 9--18 работал несколько часов, так что с 9--19 шансов нет. Но я уверен, что решения там будут.

[grizzly]

Всё ещё вожусь с алгоритмом. Выложу пока сырые достижения для поддержания монолога :)

Новый рекорд 9-20, 2520 грамм, максимальный кусок строго меньше 280.
[259, 224, 220, 206, 189, 171, 154, 140, 136, 126, 109, 101, 91, 87, 74, 60, 57, 56, 39, 21]
5: (140,126,101,60,56,21), (206,189,109), (220,136,91,57), (224,154,87,39), (259,171,74)
6: (154,140,126), (189,171,60), (206,101,57,56), (220,109,91), (224,136,39,21), (259,87,74)
7: (109,74,60,57,39,21), (126,91,87,56), (189,171), (206,154), (220,140), (224,136), (259,101)
8: (140,136,39), (154,101,60), (171,87,57), (189,126), (206,109), (220,74,21), (224,91), (259,56)
9: (136,87,57), (140,101,39), (154,126), (171,109), (189,91), (206,74), (220,60), (224,56), (259,21)

Таких рекордов у меня много. Я их теперь шинкую из своего рекорда в этой теме. Там у меня был набор из 18 элементов. Раньше я его руками резал и не нашёл решения в 20 кусков -- сделал 21. Теперь алгоритм их плодит десятками, просто разрезая куски. Таким манером нельзя получить настоящий рекорд -- я уверен. Как следствие, я уверен в наличии решения для задачи 9-19.

[sng1]

Sender в сообщении #1080215 писал(а):

Пока что там имеется три кандидата на эту роль:
A085223, A091626 и A242137.

Усилиями товарища grizzly число кандидатов сократилось.

[grizzly]

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

sng1 в сообщении #1100692 писал(а):

Усилиями товарища grizzly число кандидатов сократилось.

Пока могу добить ещё одного кандидата

Новый рекорд 10-22, 2520 грамм, максимальный кусок строго меньше 252.
[220,213,192,185,175,164,151,147,129,128,123,105,101,95,88,77,67,39,35,32,29,25]
6 guests:
(128,123,101,39,29), (164,129,95,32), (185,147,88), (192,151,77), (213,105,67,35), (220,175,25)
7 guests:
(128,88,77,67), (151,123,32,29,25), (164,101,95), (185,175), (192,129,39), (213,147), (220,105,35)
8 guests:
(128,88,67,32), (147,129,39), (164,151), (175,105,35), (185,101,29), (192,123), (213,77,25), (220,95)
9 guests:
(128,123,29), (147,101,32), (151,129), (164,77,39), (175,105), (185,95), (192,88), (213,67), (220,35,25)
10 guests:
(128,95,29), (129,123), (147,105), (151,101), (164,88), (175,77), (185,67), (192,35,25), (213,39), (220,32)

Как и предыдущее, это решение было найдено следующим способом. Взята достаточно простая для перебора задача 10-20. Почти полным перебором было найдено несколько почти-решений этой задачи (решения, в которых разбиения для каждого из $N$ гостей были без малого полными). Первое же из этих почти-решений после запуска на полный перебор двух дополнительных разрезов дало несколько искомых результатов, один из которых приведен выше.

Такой усечённый метод получения решений по-прежнему удерживает меня в убеждении, что существуют решения и для задачи 9-19, и для задачи 10-21.

Теперь, казалось бы, всё более правдоподобной выглядит гипотеза, что при переходе от чётного числа гостей $N$ к нечётному $N+1$ количество кусков в оптимальном рекорде увеличивается на 3, а при переходе от нечётного к чётному -- на 2. С каждым новым подходом к задаче моя интуиция всё громче говорит в пользу этой гипотезы, а также всё громче -- против. Поэтому я лучше брошу-таки эту задачу :) Но прежде опишу здесь вкратце все идеи, которые использовал -- вдруг кто найдёт созвучные мысли и подбросит сухих дровишек.

[grizzly]

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

1. Вариант неполного перебора.
Основная идея этого способа -- изначально генерировать для задачи N--2N (7--14, 8--16, 9--18) только те наборы, которые можно разложить на N и N-1 тарелок. Это реализуется простым алгоритмом и очень хорошо работает для N--2N задач , если искать решения без максимального куска (находятся все решения). Я пытался реализовать его и для поиска решений с максимальным куском, но в этом случае скорость заметно снижается и некоторые решения пропускаются (об этом скажу отдельно).

Схема генерации простая. Вот пример для задачи 7-14, 420 грамм. Я поясню его поэтапно под катом:

(Пример на пальцах)

Начинаем с произвольного куска К1; потом определяем К2 как 60-К1, далее К3 как 70-К2 и т.д. по циклу.

(К1) 5; (К2) 55;
(К3) 15; (К4) 45;
(К5) 25; (К6) 35;
(К7) 35; (К8) 25;
(К9) 45; (К10) 15;
(К11) 55; (К12) 5;
(К13) 60.

В итоге мы получили по горизонталям 7 тарелок по 60 грамм, а по диагоналям (снизу вверх) -- 6 тарелок по 70 грамм. Кусок К1 автоматически попал на последнюю 6-тарелку. Мы можем выбрать другую 6-тарелку для его размещения. Например, тарелку номер 4 (на которой куски К8 и К9). Нарезка тогда примет такой вид:

(К1) 5; (К2) 55;
(К3) 15; (К4) 45;
(К5) 25; (К6) 35;
(К7) 35; (К8) 25;
(К9) 40; (К10) 20; (здесь 40=70-25-5)
(К11) 50; (К12) 10;
(К13) 60.

Теперь нам нужно добавить произвольный 14-й кусок К14 и определить 7-тарелку, на которую он будет размещён. Пусть для примера кусок К14 -- 8 грамм и он размещается на пятую 7-тарелку. Получим такую нарезку:

(К1) 5; (К2) 55;
(К3) 15; (К4) 45;
(К5) 25; (К6) 35;
(К7) 35; (К8) 25;
(К9) 40; (К10) 20;
(К11) 42; (К12) 18; -- К11+К10 -- пятая 7-тарелка. На неё добавляем К14. То есть К11 = 70-20-8.
(К13) 52; (К14) 8.

Итого: мы имеем следующие свободные параметры для перебора: К1; К14; Т7(К1); Т7(К14). Тарелки варьируются от 1 до 6, куски от 1 до 30. По сравнению с полным перебором мы для задачи 7-14 уменьшили пространство перебора в ~$10^4$ раз.

Пропущенные наборы. Здесь мы неявно предположили, что структура набора, который можно разложить и на 7-, и на 6-тарелки, имеет определённый ("сильно связный") циклический характер. Это не обязательно будет так. "Граф" набора может быть не циклическим. Теоретически мы можем пропустить некоторые решения. Но сложно поверить, что наших ("хороших") решений не будет совсем, а "плохие" будут и будут пропущены. Я проверил, что для задач 7-14 и 8-16 этот алгоритм действительно ничего не пропускает и находит все решения.

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

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

[grizzly]

В продолжение предыдущего сообщения предложу теперь своё видение структуры программы полного перебора.

Проведём примитивный анализ нашей проблемы на примере задачи 9--19. Для упрощения описания будем искать решение без максимального куска. Можем считать, что на старте даны 9 тарелок по 280 грамм в каждой. Кроме этого, дан набор из 8 пустых 8-тарелок по 315 грамм, набор 7-тарелок по 360 г., и т.д. Каждая пустая тарелка представляет проблему (кроме одной в каждом наборе). Всего имеется 20 проблем ($7+6+3+4$). За один разрез можно решить не более одной проблемы одного типа (то есть точно заполнить тарелку данного типа) и, следовательно, не более 4-х проблем всего. Отметим, что решением проблемы считается также такой разрез, после которого можно сложить кратную тарелку: например, не 315 грамм, а 630 -- поскольку потом мы ещё одним разрезом сможем разделить двойную тарелку пополам. Как раз по этой причине изначально имеется только 3 проблемы с 6-тарелками (так как $280\cdot 3=420\cdot 2$).
Всего в запасе 10 разрезов.

Вышеприведённого анализа достаточно, чтобы предложить хорошую структуру программы (я надеюсь, что кто-то сможет предложить лучше). Ниже через solvedProblems#(set[],plateType) обозначена функция, которая для данного набора чисел и данного типа тарелок возвращает количество решённых проблем.

for k1= 1...140 do k2=280-k1                           -- k_i размер куска с номером i (это разрез №1)
for k3=k1...140 do k4=280-k3                           -- разрез №2 и т.д.
for k5=k3...140 do k6=280-k5
for k7=k5...140 do k8=280-k7
  if solvedProblems#(set[],8) <1 then Next end         -- здесь set[] содержит 13 элементов: k1--k8,280,...,280
for k9=k7...140 do k10=280-k9
  if solvedProblems#(set[],8) <2 then Next end
  if solvedProblems#(set[],7) <1 then Next end
...
... (остальные 5 разрезов: 3 одиночных и 1 двойной)
...
ends

На выходе этого алгоритма мы получим решение задачи. Своевременное применение функции solvedProblems#(set[],plateType) на каждом шаге отсекает основную часть вариантов бесполезного перебора.

Функция solvedProblems#(set[],plateType) является подзадачей известной и хорошо проработанной Задачи о Ранце (по ней до сих пор выходят статьи с описанием всё более эффективных алгоритмов). Я такого алгоритма написать не смог, поэтому вместо этой функции использовал простые, медленные и слишком грубые способы оценки. Следовательно, работает моя программа в десятки (сотни) раз дольше. Тем не менее задачу 7--14 считает полностью за несколько минут (в том числе решения с максимальными кусками), а задачу 8--16 за пару часов.

[sng1]

Если задано $M$ натуральных чисел, то какова трудоемкость проверки того, что эти заданные числа можно разделить на $k$ групп с одинаковой суммой?

[worm2]

Это трудный вопрос. Некоторое обобщение задачи о сумме подмножеств. Могу лишь сказать точно, что на больших числах все известные алгоритмы работают медленнее, чем $M$ в любой степени. А у нас тут уже с небольшими $M$ сложности.

[sng1]

А если надо проверить одновременно для всех $k$ от $1$ до $N$, задача не упростится?

[grizzly]

sng1 в сообщении #1179261 писал(а):

А если надо проверить одновременно для всех $k$ от $1$ до $N$, задача не упростится?

С точки зрения программиста сильно упростится -- во много раз. При тех же трудозатратах мы сможем посчитать задачу уже для $k+1$, а не для $k$ (примерно). Но вряд ли более того.

[Три А,да]

Гипотеза
Если при $n$ гостях торт разрезается на $m$ частей, то при $2n$ гостях торт разрезается на $2m+n$ частей.

[grizzly]

Три А,да в сообщении #1181656 писал(а):

Гипотеза
Если при $n$ гостях торт разрезается на $m$ частей, то при $2n$ гостях торт разрезается на $2m+n$ частей.

Странная у Вас гипотеза. Мне очевидно, что ничего похожего не будет. Вот для 5 гостей нужно 9 кусков. Тогда для 10 по Вашей гипотезе -- 28 кусков. А в теме выше было представлено несколько вариантов решений намного лучше (с текущим рекордом -- 23 куска).

[Три А,да]

Собственно там 23 и получается

[grizzly]

Три А,да в сообщении #1181868 писал(а):

Собственно там 23 и получается

Тьфу, точно, это я с арифметикой промахнулся. Но 23 было найдено вручную и это точно не минимум.

Я нисколько не сомневаюсь, что Ваша гипотеза ошибочна. Вы ведь просто решили подобрать формулу, которая бы удовлетворяла трём известным результатам из четырёх (для перехода от одного к двум формула не работает)? Или у Вас есть какие-то аргументы / что-то новое в понимании задачи? Это было бы действительно интересно.

[Три А,да]

Я так понял, что используемый алгоритм сначала делит торт на $N$ кусков, потом на $N-1$ и так далее. Эффективнее ли будет получать решение для $N$ из уже известного решения при $N-1$?