Задачка про максимальный столб из "черепах"

← →
Alx2 © (2010-06-03 10:18) [0]

Недавно довелось получить удовольствие от решения одной задачки. Делюсь:
Имеется набор черепах. Каждая черепаха обладает известной массой и известной грузоподьемностью (заданной в единицах массы). Требуется найти максимальную высоту столба из черепах (поставленных друг на друга). Алгоритм д.б. полиномиальный.

← →
oldman © (2010-06-03 12:20) [1]

Список черепах сортируем по грузоподъемности.
Далее проверяем выдержит ли каждая черепаха вес сверху, ищем предел.

← →
Alx2 © (2010-06-03 12:28) [2]

>Список черепах сортируем по грузоподъемности.
>Далее проверяем выдержит ли каждая черепаха вес сверху, ищем предел.

Ммм... 1000 кг черепаха с грузоподъемностью 100 кг раздавит нижнюю, грузоподьемностью 99 кг. А если у нас все остальные черепахи по 1 кг. и грузоподъемностью по 10 кг, то цепочка порвется преждевременно. Монстров иногда полезно выкидывать.

← →
ZeroDivide © (2010-06-03 13:14) [3]

Сортируем по массе. Двигаясь с низу, находим наименьшее соотношение Вес/грузоподъемность, ставим эту черепаху вниз, тем же способом ищем остальных черепах.

← →
Kerk © (2010-06-03 13:21) [4]

> Alx2 © (03.06.10 12:28) [2]

Зачем выкидывать, если можно поставить в самый низ?

← →
Alx2 © (2010-06-03 13:23) [5]

>Kerk © (03.06.10 13:21) [4]

Например, две черепахи по 1000 кг и грузоподъемностью 100 кг. друг на друге не удержаться.

← →
Alx2 © (2010-06-03 13:25) [6]

>ZeroDivide © (03.06.10 13:14) [3]
Знаю, здесь не любят таких фраз, но лучше б, чтобы был код. Дабы проверить идеи. Контрольные примеры я выложу вечером (решение дома лежит).

← →
Медвежонок Пятачок © (2010-06-03 13:28) [7]

несколько черепах с низкой грузоподъемностью можно уложить в один слой и получить прокачанную мета-черепаху с суммой грузоподъемностей.

← →
Alx2 © (2010-06-03 13:29) [8]

>Медвежонок Пятачок © (03.06.10 13:28) [7]

Только друг на друга :)

← →
Медвежонок Пятачок © (2010-06-03 13:32) [9]

а вообще задача неполно сформулирована.

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

← →
Медвежонок Пятачок © (2010-06-03 13:33) [10]

высота столба немного уменьшается

В том смысле, что проломлен ее панцирь.

← →
ZeroDivide © (2010-06-03 13:34) [11]

> Знаю, здесь не любят таких фраз, но лучше б, чтобы был код.
> Дабы проверить идеи. Контрольные примеры я выложу вечером
> (решение дома лежит).

Sorry, времени нет. Но идея правильная ведь да? Это задача многомерной оптимизации, первый критерий: вес/грузоподъемность, второй: вес. Т.е. нахождение локальных экстремумов, по этим двум критериям, с дальнейшей сортировкой по весу.

← →
Alx2 © (2010-06-03 13:35) [12]

Хорошо, уточню. Все черепахи должны оставаться целыми черепахами. :) Нагрузка на черепаху не должна превышать ее грузоподъемности.

← →
Alx2 © (2010-06-03 13:37) [13]

>ZeroDivide © (03.06.10 13:34) [11]

Я по-другому сделал. В твоем варианте фактически производится сортировка по соотношению Вес/грузоподъемность. И, кажется, можно подобрать контрпримеры, подобные [2]

← →
aka (2010-06-03 13:51) [14]

> Медвежонок Пятачок © (03.06.10 13:33) [10]

а коэффициент гибкости кто рассчитывать будет?

← →
ZeroDivide © (2010-06-03 13:59) [15]

> Я по-другому сделал. В твоем варианте фактически производится
> сортировка по соотношению Вес/грузоподъемность. И, кажется,
> можно подобрать контрпримеры, подобные [2]

Не так. Я же говорю второй параметр для оптимизации - вес. В математике это называется многомерной оптимизацией.

← →
Alx2 © (2010-06-03 14:03) [16]

>ZeroDivide © (03.06.10 13:59) [15]

Ok. Надо смотреть.

← →
ZeroDivide © (2010-06-03 14:35) [17]

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

Текстовый файл предлагаю нагенерить такой:
10000 черепах, с массой от 1 до 10000, кратной единице.

← →
Alx2 © (2010-06-03 14:36) [18]

>ZeroDivide © (03.06.10 14:35) [17]

:) Выдам вчером. Примерно в 20 часов.

← →
Anatoly Podgoretsky © (2010-06-03 14:39) [19]

> Alx2 (03.06.2010 13:29:08) [8]

По Фрейду

← →
ZeroDivide © (2010-06-03 14:40) [20]

... а за одно, возможно и другие подключатся. Задачка, действительно интересная...

А еще лучше сразу - тестовый файл и результат своей максимальной цепочки на этом файле. (Чтобы было на что ориентироваться :))

← →
Alx2 © (2010-06-03 14:40) [21]

>ZeroDivide © (03.06.10 14:35) [17]
>10000 черепах, с массой от 1 до 10000, кратной единице.

Боюсь, мой алгоритм сдохнет на этом стаде. :)
У меня затраты по времени O(N*(MaxMass+MaxPower))
по памяти O(MaxMass+MaxPower)
где N - мощность стада, MaxMass и MaxPower- масса и грузоподъемность черепахи с максимальной суммой массы и грузоподъемности.

Выложу менее гигантоманский вариант :)

← →
Anatoly Podgoretsky © (2010-06-03 14:40) [22]

> Медвежонок Пятачок (03.06.2010 13:33:10) [10]

Полуторная по весу, следующей ложить двухтонную.

← →
Anatoly Podgoretsky © (2010-06-03 14:41) [23]

> Alx2 (03.06.2010 13:35:12) [12]

Поздно, мы уже положили с превышением.

← →
Alx2 © (2010-06-03 14:43) [24]

>Anatoly Podgoretsky © (03.06.10 14:41) [23]

Разгружайте, звери! :)

← →
MBo © (2010-06-03 14:47) [25]

Числа целые?
Свой вес черепаху нагружает?

← →
Alx2 © (2010-06-03 14:51) [26]

>MBo © (03.06.10 14:47) [25]

Числа целые (точно, важное условие для моего варианта. с нецелыми есть только экспоненциальный вариант). Свой вес черепаху не нагружает.

PS
Ну, наконец-то ты клюнул. Я думал, в лучшем случае, напишешь две строчки кода и "молча уйдешь". :)

← →
Alx2 © (2010-06-03 14:52) [27]

Пардон, с нецелыми тоже полиномиальный. Так как стадо не может быть бесконечным. Так что получается, что целые числа - для удобства.

← →
Медвежонок Пятачок © (2010-06-03 15:52) [28]

а у черепах вообще стада или стаи?

>Медвежонок Пятачок © (03.06.10 15:52) [28]

Ну, стая - это нечто стремительное, мне кажется. Так что я склонен называть их скопления стадами :)

да..чета навскидку не придумывается ниче..
хорошая задача, домой возьму :)

> а у черепах вообще стада или стаи?

рой у них

← →
Рой медведев (2010-06-03 16:36) [33]

>рой у них

там все уже давно перерыто

А кстати - вопрос был про максимальную высоту, а высота черепах известна?

Высота в черепахах. Т.е. требуется указать максимальное кол-ва черепах.

Как я понял задачу, масса и грузоподъемность между собой собой не связаны ?

> Как я понял задачу, масса и грузоподъемность между собой
> собой не связаны ?

Связаны: нижняя черепаха не может выдержать вес, больший, чем масса верхних черепах.

Вот, тест для проверки.
Массив черепах, пары {масса, грузоподъемность}:
{8 42} {1 35} {5 70} {9 79} {5 63} {6 6} {8 82} {2 62} {3 96} {7 28} {5 92} {4 3} {3 93} {7 22} {6 19} {7 48} {9 72} {3 70} {10 68} {5 36} {2 4} {4 23} {5 74} {2 42} {9 54} {5 48} {8 63} {10 38} {2 24} {9 30} {6 17} {3 91} {7 89} {3 41} {9 65} {6 47} {10 91} {1 71} {2 7} {9 94} {4 30} {5 85} {1 57} {7 67} {9 32} {10 45} {4 27} {9 38} {3 19} {2 30}

Максимальное кол-во черепах в "столбе": 28

Решение к посту [39]:
{3 96} {3 93} {7 89} {3 91} {5 85} {5 74} {5 70} {7 67} {3 70} {1 71} {5 63} {2 62} {1 57} {5 48} {3 41} {2 42} {5 36} {1 35} {4 30} {2 30} {4 27} {4 23} {2 24} {6 17} {3 19} {2 7} {4 3} {2 4}

Задачка про максимальный столб из "черепах" Найти похожие ветки