Режем торт

[dimkadimon]

kotenok gav в сообщении #1315041 писал(а):

Можно перебирать значения кусков на компе.

Как? Пока не вижу эффективный метод для этого...

[kotenok gav]

Для каждого n - примерного числа кусков, делать такое:

Используется синтаксис Python

def f(x):
    if x==1:
        return range(1,очень большое число)
    else:
        ans=[]
        for i in f(x-1):
            k=i
            for j in range(1,очень большое число):
                k.append(j)
                ans.append(k)
        return ans
for i in f(n):
    функция проверки, подходит ли этот набор кусков

[dimkadimon]

Допустим мы хотим разбить M кусочков на N групп с одинаковой суммой. Каждый кусочек может принадлежать одной из N групп. Получается мы должны проверить $N^M$ таких разбиений, а это очень много! Каким то образом надо воспользоваться фактом что каждая группа должна иметь одну сумму...

[kotenok gav]

dimkadimon в сообщении #1315045 писал(а):

Получается мы должны проверить $N^M$ таких разбиений, а это очень много!

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

[grizzly]

dimkadimon в сообщении #1315040 писал(а):

Возник очень простой, но фундаментальный вопрос: как проверить что решение правильное?

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

Грубо говоря так: рассматриваем задачу 7--14, начинаем на старте с 420 элементарных кусочков; пусть эти 420 э.к. поделены на 7 гостей. Значит каждый из 7 гостей получит 60 э.к. Вот уже часть нарезки определена. Дальше нужно, чтобы эти 7х60 можно было превратить в 6х70. Тогда пытаемся поделить каждый из уже полученных на какие-то части, чтобы из них можно было сложить 6х70. Поскольку количество таких дополнительных разрезов ограничено сверху числом 7 (раз задача 7--14, а 7 из 14 разрезов мы уже имеем) вариантов с учётом симметрий не так много. Действуя таким образом дальше, к концу получим решение, которое не требует перепроверки.

[dimkadimon]

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

[grizzly]

dimkadimon в сообщении #1315059 писал(а):

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

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

[grizzly]

(Торт да не торт)

Не совсем в тему, но забавно, что выпуклый торт можно поделить на куски равной площади и периметра (или объёма и площади поверхности, если кому так вкуснее :)

[dimkadimon]

Нашёл быстрый метод проверки решений и это мне позволило найти 9-19!

21 56 69 85 95 101 115 119 120 130 150 155 160 161 165 179 185 195 259
guests=5: 259+160+85 = 195+179+130 = 185+155+95+69 = 165+161+101+56+21 = 150+120+119+115
guests=6: 259+161 = 195+130+95 = 185+179+56 = 165+101+85+69 = 160+120+119+21 = 155+150+115
guests=7: 259+101 = 195+165 = 185+119+56 = 179+160+21 = 161+130+69 = 155+120+85 = 150+115+95
guests=8: 259+56 = 195+120 = 185+130 = 179+115+21 = 165+150 = 161+85+69 = 160+155 = 119+101+95
guests=9: 259+21 = 195+85 = 185+95 = 179+101 = 165+115 = 161+119 = 160+120 = 155+69+56 = 150+130

[kotenok gav]

dimkadimon в сообщении #1315472 писал(а):

быстрый метод проверки решений

Какой?

[dimkadimon]

Я использую обычный depth first search. Секрет скорости это ранее обрезание плохих вариантов. Например мы знаем что в полном решение каждое число должно использоваться. Если одно число не подходит (например самое большое выше нужной суммы) то поиск можно сразу прекращать.

[grizzly]

dimkadimon в сообщении #1315472 писал(а):

Нашёл быстрый метод проверки решений и это мне позволило найти 9-19!

Вот это да! Ещё бы 10-21 найти и я буду спокойно считать, что моя гипотеза верна :)

Точно не помню, но кажется, что я достаточно плотно проверил 9-18 на отсутствие решений. В 10-20 тоже не верю.

[kotenok gav]

Сегодня-завтра напишу программу.

[Sender]

dimkadimon в сообщении #1315472 писал(а):

Нашёл быстрый метод проверки решений и это мне позволило найти 9-19!

Потрясающе, новый мировой рекорд! Надо обрадовать профессоров. Кстати, интересно, не помогут ли SAT-решателям эти дополнительные ограничения быстрее добраться до ответа? Как будет время, проверю обязательно.

[12d3]

Приятно возвращаться к задачке через долгое время, с новыми идеями.
Вроде как удалось выполнить полный перебор для 8-16, найдено 8 решений, из которых 2 новых.

1 10 14 25 29 41 44 49 56 61 64 76 79 91 95 105
1 14 25 29 34 41 44 49 56 61 64 71 76 79 91 105
2 17 25 32 37 38 47 52 53 58 67 68 73 80 88 103
4 11 25 26 31 41 44 46 59 61 64 74 76 79 94 105
6 9 10 21 25 36 41 49 56 64 69 71 84 95 99 105
6 9 21 25 26 36 41 49 56 64 69 71 79 84 99 105
11 25 26 29 31 41 44 46 59 61 64 74 76 79 80 94
17 23 25 32 37 38 47 52 53 58 67 68 73 80 82 88

Только один минус есть. У меня в процессе поиска решений нигде не хранились собственно разбиения на группы, и отдельной функции проверки решения я не писал. Так что придется пока верить на слово.

-- Пн май 28, 2018 23:43:52 --

UPD.
Написал проверку решений.

(Оффтоп)

1 10 14 25 29 41 44 49 56 61 64 76 79 91 95 105
49+56 = 44+61 = 41+64 = 29+76 = 1+25+79 = 14+91 = 10+95 = 105
10+49+61 = 56+64 = 44+76 = 41+79 = 29+91 = 25+95 = 1+14+105
14+29+41+56 = 64+76 = 61+79 = 49+91 = 1+44+95 = 10+25+105
10+41+56+61 = 25+64+79 = 1+76+91 = 29+44+95 = 14+49+105

1 14 25 29 34 41 44 49 56 61 64 71 76 79 91 105
49+56 = 44+61 = 41+64 = 34+71 = 29+76 = 1+25+79 = 14+91 = 105
25+34+61 = 56+64 = 49+71 = 44+76 = 41+79 = 29+91 = 1+14+105
14+29+41+56 = 25+44+71 = 64+76 = 61+79 = 49+91 = 1+34+105
29+34+44+61 = 41+56+71 = 25+64+79 = 1+76+91 = 14+49+105
14+44+49+61 = 41+56+71 = 25+64+79 = 1+76+91 = 29+34+105

2 17 25 32 37 38 47 52 53 58 67 68 73 80 88 103
52+53 = 47+58 = 38+67 = 37+68 = 32+73 = 25+80 = 17+88 = 2+103
25+37+58 = 53+67 = 52+68 = 47+73 = 2+38+80 = 32+88 = 17+103
17+32+38+53 = 25+47+68 = 67+73 = 2+58+80 = 52+88 = 37+103
17+32+52+67 = 47+53+68 = 37+58+73 = 80+88 = 2+25+38+103

4 11 25 26 31 41 44 46 59 61 64 74 76 79 94 105
46+59 = 44+61 = 41+64 = 31+74 = 4+25+76 = 26+79 = 11+94 = 105
59+61 = 25+31+64 = 46+74 = 44+76 = 41+79 = 26+94 = 4+11+105
11+26+44+59 = 25+41+74 = 64+76 = 61+79 = 46+94 = 4+31+105
11+26+41+44+46 = 31+61+76 = 25+64+79 = 74+94 = 4+59+105

6 9 10 21 25 36 41 49 56 64 69 71 84 95 99 105
49+56 = 41+64 = 36+69 = 9+25+71 = 21+84 = 10+95 = 6+99 = 105
56+64 = 10+41+69 = 49+71 = 36+84 = 25+95 = 21+99 = 6+9+105
6+21+49+64 = 69+71 = 56+84 = 9+36+95 = 41+99 = 10+25+105
41+56+71 = 10+25+49+84 = 9+64+95 = 69+99 = 6+21+36+105

6 9 21 25 26 36 41 49 56 64 69 71 79 84 99 105
49+56 = 41+64 = 36+69 = 9+25+71 = 26+79 = 21+84 = 6+99 = 105
56+64 = 25+26+69 = 49+71 = 41+79 = 36+84 = 21+99 = 6+9+105
6+21+49+64 = 69+71 = 25+36+79 = 56+84 = 41+99 = 9+26+105
41+56+71 = 25+64+79 = 9+26+49+84 = 69+99 = 6+21+36+105

11 25 26 29 31 41 44 46 59 61 64 74 76 79 80 94
46+59 = 44+61 = 41+64 = 31+74 = 29+76 = 26+79 = 25+80 = 11+94
59+61 = 25+31+64 = 46+74 = 44+76 = 41+79 = 11+29+80 = 26+94
11+26+44+59 = 25+41+74 = 64+76 = 61+79 = 29+31+80 = 46+94
11+26+41+44+46 = 31+61+76 = 25+64+79 = 29+59+80 = 74+94

17 23 25 32 37 38 47 52 53 58 67 68 73 80 82 88
52+53 = 47+58 = 38+67 = 37+68 = 32+73 = 25+80 = 23+82 = 17+88
25+37+58 = 53+67 = 52+68 = 47+73 = 17+23+80 = 38+82 = 32+88
17+32+38+53 = 25+47+68 = 67+73 = 23+37+80 = 58+82 = 52+88
17+32+52+67 = 47+53+68 = 37+58+73 = 23+25+38+82 = 80+88