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

← →
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]

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

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

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

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

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

>Медвежонок Пятачок © (03.06.10 15:52) [28]
И вообще стеб здесь опасен: http://i.postnext.com/img_set13/ww11111s_003.jpg

← →
12 © (2010-06-03 16:18) [31]

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

← →
DVM © (2010-06-03 16:33) [32]

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

рой у них

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

>рой у них

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

← →
icWasya © (2010-06-03 17:18) [34]

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

← →
Alx2 © (2010-06-03 17:19) [35]

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

← →
Jeer © (2010-06-03 18:16) [36]

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

← →
ZeroDivide © (2010-06-03 19:01) [37]

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

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

← →
Alx2 © (2010-06-03 19:57) [38]

>Jeer © (03.06.10 18:16) [36]

Да. Для черепахи собственная масса и собственная грузоподъемность не связаны.

← →
Alx2 © (2010-06-03 20:03) [39]

Вот, тест для проверки.
Массив черепах, пары {масса, грузоподъемность}:
{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

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

Решение к посту [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}

← →
Alx2 © (2010-06-03 20:28) [41]

Тест посерьезнее. кол-во черепах 500.
Черепахи:
{68 2} {1 15} {25 10} {59 19} {65 3} {46 6} {28 2} {92 2} {43 16} {37 8} {5 12} {54 3} {83 13} {17 2} {96 19} {27 8} {39 12} {13 10} {100 8} {95 16} {12 4} {34 3} {65 14} {12 2} {69 14} {45 8} {58 3} {60 18} {42 4} {79 10} {36 17} {43 11} {7 9} {43 1} {49 5} {6 7} {30 11} {51 11} {2 7} {49 14} {24 10} {55 5} {41 17} {77 7} {9 12} {40 5} {24 7} {39 18} {83 19} {42 10} {16 14} {59 20} {31 5} {7 18} {87 14} {46 2} {73 5} {30 11} {74 18} {13 18} {91 7} {37 2} {68 16} {75 16} {53 12} {51 11} {25 2} {31 7} {92 8} {38 8} {88 18} {84 14} {10 6} {59 10} {89 2} {47 3} {31 7} {69 14} {92 1} {56 3} {60 11} {38 5} {84 9} {42 16} {51 3} {37 12} {21 15} {22 17} {100 9} {85 9} {35 2} {100 14} {39 19} {89 1} {68 8} {94 9} {84 9} {22 8} {18 11} {15 14} {17 10} {52 16} {50 1} {57 20} {4 19} {9 5} {10 5} {3 10} {86 16} {44 14} {88 4} {4 15} {1 9} {19 19} {97 1} {82 19} {99 10} {58 10} {23 13} {93 19} {80 19} {58 11} {92 19} {89 16} {12 17} {35 3} {56 13} {47 9} {87 3} {34 16} {43 10} {17 5} {99 2} {52 3} {100 2} {77 18} {90 13} {13 16} {11 1} {70 4} {89 2} {90 2} {24 16} {86 3} {86 3} {27 9} {58 18} {33 13} {55 10} {90 2} {30 17} {93 9} {56 6} {50 15} {13 2} {61 6} {54 19} {24 20} {97 20} {30 8} {38 10} {50 7} {96 14} {17 18} {6 7} {83 9} {35 16} {2 15} {72 17} {64 7} {56 14} {54 6} {9 13} {46 13} {57 14} {59 2} {83 7} {45 2} {23 17} {62 10} {51 16} {67 14} {60 5} {40 13} {25 14} {11 15} {50 6} {14 7} {23 15} {19 9} {6 8} {92 19} {26 3} {15 18} {25 15} {75 15} {60 13} {71 14} {98 8} {78 19} {71 14} {69 4} {86 13} {81 3} {28 14} {100 3} {26 8} {25 4} {73 4} {82 2} {33 4} {94 6} {32 6} {43 13} {87 3} {1 5} {61 8} {75 14} {71 11} {34 16} {61 12} {68 17} {51 6} {95 1} {25 16} {26 20} {95 17} {3 19} {67 12} {94 19} {85 12} {65 19} {53 20} {88 1} {27 1} {58 11} {16 11} {28 17} {59 4} {10 5} {87 3} {88 6} {75 18} {28 6} {29 10} {21 4} {63 3} {97 4} {62 18} {26 16} {61 5} {17 3} {27 11} {72 12} {48 12} {21 14} {25 11} {64 9} {52 1} {30 3} {14 1} {79 19} {8 6} {1 18} {40 19} {61 4} {25 18} {9 18} {88 14} {51 2} {29 1} {85 14} {41 6} {5 12} {57 16} {51 13} {86 4} {17 17} {58 7} {58 7} {72 18} {62 10} {23 17} {13 18} {97 18} {42 6} {30 4} {66 10} {33 20} {56 17} {63 14} {35 5} {73 15} {70 18} {64 13} {84 8} {36 12} {49 8} {39 16} {43 4} {12 15} {76 2} {26 20} {71 2} {35 7} {84 6} {99 11} {2 20} {35 14} {35 18} {94 17} {6 17} {49 3} {1 2} {42 14} {56 16} {63 3} {78 12} {79 5} {44 13} {74 17} {14 1} {73 16} {11 19} {33 18} {96 13} {32 10} {89 1} {91 6} {90 18} {46 11} {15 14} {41 12} {59 5} {60 16} {6 13} {82 5} {30 4} {9 16} {98 13} {57 10} {28 2} {42 8} {41 10} {75 14} {78 2} {84 16} {93 14} {2 5} {60 13} {29 11} {85 8} {87 16} {71 19} {48 8} {4 5} {64 2} {64 7} {72 11} {41 10} {43 5} {14 20} {5 12} {33 19} {6 11} {40 16} {23 4} {48 19} {49 5} {65 12} {76 14} {13 6} {79 7} {63 10} {86 20} {45 10} {41 6} {9 6} {71 19} {24 2} {73 13} {88 13} {64 11} {4 2} {28 4} {70 1} {66 16} {44 9} {89 8} {38 4} {64 10} {82 10} {43 9} {61 9} {59 2} {89 15} {91 7} {44 10} {21 11} {68 9} {84 17} {27 16} {39 6} {30 14} {49 5} {60 4} {67 18} {56 5} {27 19} {26 12} {2 16} {97 10} {16 5} {43 5} {14 16} {97 3} {73 9} {7 7} {30 14} {6 5} {13 7} {94 16} {37 6} {42 17} {95 15} {53 17} {39 17} {56 3} {32 16} {42 11} {12 6} {87 18} {51 11} {35 3} {54 14} {53 17} {63 9} {55 14} {35 4} {57 4} {25 9} {14 18} {29 10} {81 1} {59 19} {56 11} {65 2} {77 4} {10 4} {62 3} {49 10} {54 3} {21 15} {24 3} {70 12} {60 19} {20 9} {4 12} {82 6} {93 5} {14 6} {90 19} {39 3} {11 18} {35 2} {62 9} {94 20} {70 16} {70 18} {1 19} {65 12} {16 18} {16 16} {40 11} {89 13} {55 3} {11 6} {75 5} {16 1} {42 12} {80 16} {99 11} {89 14} {33 18} {90 17} {9 14} {91 2} {64 4} {85 9} {1 19} {86 12} {72 15} {68 14} {96 14} {26 9} {30 17} {99 11} {94 10} {81 7} {50 17}

Высота максимального столба: 14 черепах
Решение:
{14 20} {2 20} {1 19} {1 19} {1 18} {2 16} {2 15} {1 15} {3 10} {1 9} {2 7} {2 5} {1 5} {1 2}

← →
Sha © (2010-06-04 01:20) [42]

Тупой перебор (ничего умнее пока нет)
type TPlaceArray= array of integer; PTurtle= ^TTurtle; TTurtle= record w: integer; //weight c: integer; //carrying p: integer; //previous b: integer; //best end; var a: array of TTurtle; best, first: integer; procedure TurtleLoad; var i: integer; begin; SetLength(a,50); Randomize; for i:=0 to Length(a)-1 do begin; a[i].w:=Random(20)+1; a[i].c:=Random(20)+1; end; end; function FirstIsUpper(p1, p2: PTurtle): boolean; var m1, m2: integer; begin; m1:=p1.c-p2.w; if m1>p2.c then m1:=p2.c; m2:=p2.c-p1.w; if m2>p1.c then m2:=p1.c; Result:=m1<m2; end; procedure TurtleSort; var t: TTurtle; i: integer; done: boolean; begin; repeat; done:=true; for i:=0 to Length(a)-2 do if FirstIsUpper(@a[i],@a[i+1]) then begin; t:=a[i]; a[i]:=a[i+1]; a[i+1]:=t; done:=false; end; until done; end; procedure TurtleSolution(previous, count: integer); var weight, i, j: integer; begin; for i:=previous+1 to Length(a)-1 do begin; j:=i; weight:=0; a[i].p:=previous; repeat; weight:=weight+a[j].w; j:=a[j].p; until (j<0) or (weight>a[j].c); if j<0 then TurtleSolution(i, count+1); end; if best<count then begin; best:=count; first:=previous; j:=first; repeat; a[j].b:=a[j].p; j:=a[j].p; until j<0; end; end; procedure TForm1.Button1Click(Sender: TObject); var i: integer; begin; TurtleLoad; TurtleSort; best:=0; first:=-1; TurtleSolution(-1, 0); Memo1.Lines.Clear; Memo1.Lines.Add(" weight carrying"); Memo1.Lines.Add("-------------------------------"); for i:=0 to Length(a)-1 do Memo1.Lines.Add(Format("%.2d %.2d %.2d",[i, a[i].w, a[i].c])); Memo2.Lines.Clear; Memo2.Lines.Add(Format("count = %d",[best])); Memo2.Lines.Add(" weight carrying"); Memo2.Lines.Add("-------------------------------"); i:=first; while i>=0 do begin; Memo2.Lines.Add(Format("%.2d %.2d %.2d",[i, a[i].w, a[i].c])); i:=a[i].b; end; end;

← →
MBo © (2010-06-04 08:00) [43]

>Ну, наконец-то ты клюнул.
Ну ветку-то я сразу увидел, смахивает на ДП, однако ступор с возможностью выделения оптимальных субзадач, и пока не удается под разными углами задачу рассмотреть...

← →
Alx2 © (2010-06-04 08:11) [44]

>MBo © (04.06.10 08:00) [43]
>смахивает на ДП

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

Кстати, Sha © в (04.06.10 01:20) [42] вроде сильно подкрался :) Но у меня вроде по другому признаку сортируются (хотя, не уверен - может статься, что эквивалентно - не проверял).

← →
Sha © (2010-06-04 09:39) [45]

Alx2 © (04.06.10 08:11) [44]

У меня сначала были сомнения, что отношение "выгоднее быть сверху" транзитивно.
Для доказательства надо много случаев рассмотреть, а на первый взляд не очевидно.
Вместо доказательства проверял на миллиарде случайных троек черепах:
procedure TForm1.Button2Click(Sender: TObject); var ok: boolean; t: array[0..2] of TTurtle; i, j, k: integer; begin; Randomize; for k:=1 to 1000000000 do begin; for i:=0 to 2 do begin; t[i].w:=Random(99)+1; t[i].c:=Random(99)+1; end; if FirstIsUpper(@t[0],@t[1]) then if FirstIsUpper(@t[1],@t[2]) then ok:=FirstIsUpper(@t[0],@t[2]) else ok:=true else if FirstIsUpper(@t[0],@t[2]) then ok:=FirstIsUpper(@t[1],@t[2]) else ok:=true; if not ok then begin; for j:=0 to 2 do Memo1.Lines.Add(Format("%.2d %.2d %.2d",[j, t[j].w, t[j].c])); end; end; Memo1.Lines.Add("Done"); end;

← →
pasha_golub © (2010-06-04 09:58) [46]

> Sha © (04.06.10 09:39) [45]

> Вместо доказательства проверял на миллиарде случайных троек
> черепах:

Во! Вот это по нашему :))

← →
Sha © (2010-06-04 10:02) [47]

pasha_golub © (04.06.10 09:58) [46]

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

← →
Alx2 © (2010-06-04 10:16) [48]

>Sha © (04.06.10 10:02) [47]

Кстати, насколько быстро получилось? Можешь дать оценку сложности?

У меня с выводом решения сложность по памяти и по времени = O(N*(MaxMass+MaxPower)) N - кол-во черепах, MaxPower и MaxMass - максимум грузоподъемности с массой.
Для вывода кол-ва черепах в максимальном столбе исользуется O(MaxMass+MaxPower) памяти и O(N*(MaxMass+MaxPower)) времени.

← →
Sha © (2010-06-04 10:25) [49]

> Alx2 © (04.06.10 10:16) [48]
> Кстати, насколько быстро получилось? Можешь дать оценку сложности?

Память расходуется только под массив черепах и стек без разветвлений, поэтому O(N).
Время - перебор всех подмножеств с отсечением - не хуже O(2^N).
Есть ощущение, что и время, и оценку можно существенно улучшить.

← →
Alx2 © (2010-06-04 10:42) [50]

Я сортирую по сумме грузоподъемности и массы. По убыванию. Затем выбираю подпоследовательность максимальной длины, в которой выполняется условие "живучести" черепах.

Сортирую так вот почему:
Идея в том, чтобы внизу столба были черепахи, максимально обеспечивающие "запас прочности".

Обозначу как (m[k],p[k]) k-ю черепаху с грузоподъемностью p[k] и массой m[k].
Пусть S - сумма масс всех черепах. То есть S = sum(m[k], k = 1..N);

Далее выбираю такую черепаху, для которой был максимальный "запас прочности" по удержанию оставшегося столба. Пусть j - номер черепахи. Тогда j должен быть таким:
p[j] - (sum(m[k],k=1..N) - m[j]) -> max
или
p[j]+m[j] - sum(m[k],k=1..N) - > max
или
p[j]+m[j] - S - > max
или
p[j]+m[j] -> max

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

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

← →
KilkennyCat © (2010-06-04 10:44) [51]

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

← →
Alx2 © (2010-06-04 10:47) [52]

>KilkennyCat © (04.06.10 10:44) [51]

Уже был подобный вопрос. Учитывается только кол-во черепах :)

← →
ZeroDivide © (2010-06-04 10:50) [53]

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

Считаем количество, т.е ищем максимально длинную цепочку.

Но вообще, вынос мозга... я пока в ступоре.

← →
Anatoly Podgoretsky © (2010-06-04 11:18) [54]

> KilkennyCat (04.06.2010 10:44:51) [51]

Пробовали, скатываются

← →
aka (2010-06-04 11:58) [55]

Все зависит от банды черепах, если их не много то можно:

var max_stolb;

1) делать массив вариантов расстановок (факториал от количества)

2) в каждом варианте подлаживая одну черепаху, проверять вариант(массив) с самого начала на предмет аварии.

3) постоянно сравнивать max_stolb каждого варианта расстановки

4) вывести max_stolb.

вариант - железо, не вызывает не каких сомнений поводу оптимальности.)

Голосуйте за мой вариант!

← →
Sha © (2010-06-04 12:04) [56]

Нашел :)
Matrix[i,m-1] содержит высоту стопки весом m черепах с номерами, большими i
Заполняется так:
Matrix[i,m-1]:=Matrix[i+1,m-1], если i-тая черепаха не входит в стопку массой m
Matrix[i,m-1]:=Matrix[i+1,m-1-a[i].w]+1, если входит
Будет время, напишу решение.

← →
Sha © (2010-06-04 12:11) [57]

> aka (04.06.10 11:58) [55]
> делать массив вариантов расстановок (факториал от количества)

100!
делать - не переделать

← →
Anatoly Podgoretsky © (2010-06-04 12:16) [58]

> Sha (04.06.2010 12:04:56) [56]

Это сколько же черепах влезет в яму?
http://delphimaster.net/view/15-1275598450/ Двадцать
второе сообщение.

← →
aka (2010-06-04 12:19) [59]

> Sha © (04.06.10 12:11) [57]

Так сколько черепах? Я в "Мире животных" видел не больше 7 - ми

← →
Anatoly Podgoretsky © (2010-06-04 12:22) [60]

> aka (04.06.2010 12:19:59) [59]

Так то в мире животных.

← →
Sha © (2010-06-04 12:23) [61]

> Anatoly Podgoretsky © (04.06.10 12:16) [58]
> Это сколько же черепах влезет в яму?

Зависит от тестового массива Alx2,
кто знает какие годзиллы у него на уме? )

> aka (04.06.10 12:19) [59]
> Так сколько черепах? Я в "Мире животных" видел не больше 7 - ми

На случайных данных для 100 черепах чаще всего получается этажерка 10-15 штук.

← →
Alx2 © (2010-06-04 12:32) [62]

>Sha © (04.06.10 12:04) [56]

Здорово. Практически совпало с моим. С нюансами, которые пофиксятся при проверке. :)

← →
Sha © (2010-06-04 12:50) [63]

> Alx2 © (04.06.10 10:42) [50]
> Затем выбираю подпоследовательность максимальной длины, в которой выполняется условие "живучести" черепах.

До [56] мне было неясно, как при этом обойтись без перебора,
например, на таких черепахах: 04 44 78 87

← →
aka (2010-06-04 13:35) [64]

Не верю что нигде не описано решение этой задачи в какой то из книг по алгоритмам,
типа как "Задача о восьми ферзях" в "Алгоритмы и структуры данный" Н.Вирт

← →
Alx2 © (2010-06-04 13:36) [65]

2 aka (04.06.10 13:35) [64]

Даже не искал. Задачка попала от коллеги. Вроде как на какой-то олимпиаде мелькала. Для олимпиад не берут "бояны". Хотя, от боянистых принципов в решении все равно не уйти.

← →
aka (2010-06-04 13:57) [66]

А затем для каждой черепашки:

Черепашка находится в городе, все кварталы которого
имеют прямоугольную форму, и ей необходимо попасть с
крайнего северо-западного перекрестка на крайний юго-
восточный. На некоторых улицах проводится ремонт, и
по ним запрещено движение (например, между перекрес-
тками 3 и 7, 5 и 6, 10 и 11), длина, а значит и стоимость
проезда по остальным улицам задается. Кроме того, для
каждого перекрестка определена стоимость поворота. Так,
если Черепашка пришла на 7-й перекресток и поворачива-
ет к 11-му, то она платит штраф, а если идет в направлении
8-го, то платить ей не приходится. Найти для Черепашки
маршрут минимальной стоимости.

← →
Alx2 © (2010-06-04 14:05) [67]

aka (04.06.10 13:57) [66]
navitel.su :)

← →
aka (2010-06-04 14:08) [68]

> navitel.su :)

не помню уже

← →
Sha © (2010-06-04 14:14) [69]

aka (04.06.10 13:57) [66]

Как раз это фигня.
Считаешь потенциалы перекрестков и все.

← →
KilkennyCat © (2010-06-04 14:57) [70]

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

← →
aka (2010-06-04 15:07) [71]

> между черепашками

не нужно это учитывать, это очень и очень мало

← →
Jeer © (2010-06-04 15:11) [72]

> KilkennyCat © (04.06.10 14:57) [70]
>
> Между прочим, в разных местах

Тема пола черепашек не раскрыта.

← →
Sha © (2010-06-04 16:02) [73]

ДП в чистом виде.

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

//Matrix[i,m] содержит высоту стопки весом m или меньше черепах с номерами i или больше //Matrix[i,m]:=Matrix[i+1,m], если i-тая черепаха не входит в стопку массой m //Matrix[i,m]:=Matrix[i+1,m-a[i].w]+1, если входит Matrix: array of array of integer; procedure FillMatrix; var i, m, m1, m2, m3, count: integer; begin; SetLength(Matrix,Length(a)); i:=Length(a)-1; m:=a[i].w; SetLength(Matrix[i],m+1); Matrix[i,m]:=1; while m>0 do begin; dec(m); Matrix[i,m]:=0; end; dec(i); while i>=0 do begin; m1:=Length(Matrix[i+1])-1; m:=a[i].c+a[i].w; if m<m1 then m:=m1; SetLength(Matrix[i], m+1); while m>=0 do begin; m3:=m; if m3>m1 then m3:=m1; count:=Matrix[i+1,m3]; m2:=m-a[i].w; m3:=m2; if m3>m1 then m3:=m1; if (m2>=0) and (m2<=a[i].c) and (count<=Matrix[i+1,m3]) then count:=Matrix[i+1,m3]+1; Matrix[i,m]:=count; dec(m); end; dec(i); end; end; procedure FindSolution; var i, imax, m, m1, count: integer; begin; first:=-1; best:=0; m:=Length(Matrix[0])-1; imax:=Length(Matrix)-1; for i:=0 to imax do begin; count:=Matrix[i,m]; if count=0 then break; while (m>0) and (count=Matrix[i,m-1]) do dec(m); if i<imax then begin; m1:=Length(Matrix[i+1])-1; if m1>m then m1:=m; if Matrix[i+1,m1]=count then begin; m:=m1; continue; end; end; inc(best); a[i].b:=first; first:=i; m:=m-a[i].w; end; end;

← →
Alx2 © (2010-06-04 16:13) [74]

>Sha © (04.06.10 16:02) [73]

Фигассе, без сортировки и O(N*Mass)... Мне снова есть куда расти :)

К Alx2 © (04.06.10 16:13) [74]
Поправка. Все-таки сложность как у меня: O(N*(MaxMass+MaxPower)). Но без использования сортировки.

>Sha © (04.06.10 17:47) [77]

>O(N * Max(Mass[i]+Power[i]) )

Ага, я это имел в виду. У меня столько же. + сортировка. Код на ночь глядя выложу :)

Интересно, что если от силы панциря перейти к силе ног:
сила ног = сила панциря + собственный вес,
то задача решалась бы очевидным упорядочиванием по силе ног.

Кстати, проверил, FirstIsUpper совпала с силой ног
на миллионе наборов по 100 черепашек.

> Alx2 © (04.06.10 17:52) [78]
> Ага, я это имел в виду. У меня столько же. + сортировка. Код на ночь глядя выложу :)

Так и у меня требуется предварительная сортировка:
либо как FirstIsUpper (по большей силе панциря комбинации из двух черепашек),
либо по силе ног, что эквивалентно.

> Alx2 © (03.06.10 20:14) [40]
>
> Решение к посту [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}

У меня получилось так:
Номер: Вес - Грузоподъемность - Давящая масса
1: 2 - 4 - 0
2: 2 - 7 - 2
3: 3 - 19 - 4
4: 6 - 19 - 7
5: 4 - 23 - 13
6: 2 - 24 - 17
7: 4 - 27 - 19
8: 2 - 30 - 23
9: 4 - 30 - 25
10: 1 - 35 - 29
11: 5 - 36 - 30
12: 3 - 41 - 35
13: 2 - 42 - 38
14: 6 - 47 - 40
15: 5 - 48 - 46
16: 1 - 57 - 51
17: 2 - 62 - 52
18: 5 - 63 - 54
19: 3 - 70 - 59
20: 5 - 70 - 62
21: 1 - 71 - 67
22: 5 - 74 - 68
23: 5 - 85 - 73
24: 7 - 89 - 78
25: 3 - 91 - 85
26: 5 - 92 - 88
27: 3 - 93 - 93
28: 3 - 96 - 96

1: 1 - 2 - 0
2: 1 - 5 - 1
3: 2 - 5 - 2
4: 2 - 7 - 4
5: 1 - 9 - 6
6: 1 - 15 - 7
7: 2 - 15 - 8
8: 2 - 16 - 10
9: 1 - 18 - 12
10: 1 - 19 - 13
11: 1 - 19 - 14
12: 3 - 19 - 15
13: 2 - 20 - 18
14: 14 - 20 - 20

Вот мой вариант (сорри за C++):

class Turtle{ public: int mass, power; Turtle(){ } Turtle(int mass, int power){ this->mass = mass; this->power = power; } bool operator>(const Turtle &source) const{ return mass+power<source.mass+source.power; } bool operator<(const Turtle &source) const{ return mass+power>source.mass+source.power; } }; int polyVal(vector <Turtle> &turtles){ sort(turtles.begin(),turtles.end()); int turtleSize = (int)turtles.size(); int maxPower = 0; for (int k=0;k<turtleSize; k++) maxPower = max(maxPower,turtles[k].power+turtles[k].mass); int *r1,*r2; r1 = new int [maxPower+1]; r2 = new int [maxPower+1]; for (int k=0;k<=maxPower;k++) r1[k] = 0; for (int idx=turtleSize-1;idx>=0;idx--){ Turtle &t = turtles[idx]; r2[0] = 0; for (int k=1;k<=maxPower;k++){ int rest = min(t.power,k-t.mass); if (rest>=0) r2[k] = max(1+r1[rest],r1[k]); else r2[k]=r1[k]; } swap(r1,r2); } int result = r1[maxPower]; delete[] r1; delete[] r2; return result; }

ZeroDivide © (04.06.10 21:00) [82]
Классно! Главное, длина равна максимальной. А оптимальный решений может быть множество.

Sha © (04.06.10 18:18) [80]

То есть практически то, что я писал в [50]? И подтвердилась эквивалентность с отмеченным в [44]?

Ощущение, что мы совпали полностью (после твоего заамечания про сортировку ) :)

> Alx2 © (04.06.10 22:32) [88]
> То есть практически то, что я писал в [50]?
> И подтвердилась эквивалентность с отмеченным в [44]?

Да.

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

Твое ставит вниз ту, у которой крепче ноги.

Оказалось, что это одно и тоже, но твое вычислять проще.

Alx2 © (04.06.10 22:27) [85]
Как обычно, вдогонку к самому себе.
Вот это лишнее:
for (int k=0;k<turtleSize; k++) maxPower = max(maxPower,turtles[k].power+turtles[k].mass);
так как искомое уже лежит в нулевом элементе :)
То есть заменяется на
int maxPower = turtles[0].mass+turtles[0].power;

Таких бы веток побольше)

TTurtle = record Weight: Word; Cargo: Word; WC: Longword; Used: Boolean; end; ... procedure TfmMain.PrepareTurtles; var n, m, z: Integer; TempTurtle: TTurtle; Sorted: boolean; CurrentWeight: Integer; LocalIndex: Integer; MinWeight, MaxWeight, PreMaxWeight: Integer; function InCondition: boolean; var m: Integer; TopFound: boolean; begin Result := True; // CurrentWeight := ResultTurtles[0].Weight; TopFound := False; for m := 0 to Length(ResultTurtles) - 1 do begin if ResultTurtles[m].Used then begin if not TopFound then begin CurrentWeight := ResultTurtles[m].Weight; TopFound := True end else if CurrentWeight > ResultTurtles[m].Cargo then Result := False else CurrentWeight := CurrentWeight + ResultTurtles[m].Weight; end; end; end; begin MinWeight := Turtles[0].Weight; MaxWeight := 1; //Сортируем по грузоподъемности и весу // В Turtles[m].WC - для сортировки по обоим значениям, // при загрузке и парсинге файла с черепашками, было прописано // Turtles[m].WC := Turtles[m].Cargo*$FFFF; // Turtles[m].WC := Turtles[m].WC + Turtles[m].Weight; repeat Sorted := True; for n := 0 to Length(Turtles)-2 do begin if Turtles[n].WC > Turtles[n+1].WC then begin TempTurtle := Turtles[n]; Turtles[n] := Turtles[n+1]; Turtles[n+1] := TempTurtle; Sorted := False; end; if MinWeight > Turtles[n].Weight then MinWeight := Turtles[n].Weight; if MaxWeight < Turtles[n].Weight then MaxWeight := Turtles[n].Weight; end; until Sorted; //Из всего списка черепашек, перекидываем в результирующий //массив черепашек по мере утяжеления их веса, при этом //сохраняя их позицию в массиве SetLength(ResultTurtles, Length(Turtles)); LocalIndex := 0; for n := MinWeight to MaxWeight do begin //Записываем самых легких черепашек в итоговую таблицу for m := Length(Turtles) - 1 downto 0 do if (not ResultTurtles[m].Used) and (Turtles[m].Weight = n) then begin ResultTurtles[m] := Turtles[m]; ResultTurtles[m].Used := True; end; //Проверяем выполнение условия сохранения столба //Наступил пипец, условие не выполняется if not InCondition then begin //На каком весе он наступил LocalIndex := n; Break; end; end; //Столб уже построен, задействованы все черепашки if LocalIndex = 0 then Exit; // Разгружаем черепах с LocalIndex начиная сверху, // пока столб не будет удовлетворять условию for n := 0 to Length(Turtles) - 1 do begin if (ResultTurtles[n].Used) and (ResultTurtles[n].Weight = LocalIndex) then begin ResultTurtles[n].Used := False; if InCondition then Break; end; end; //Сколько недогружено на последней черепахе //И сколько на нее давит CurrentWeight := 0; z := 0; for m := 0 to Length(ResultTurtles) - 1 do if ResultTurtles[m].Used then begin z := CurrentWeight; CurrentWeight := CurrentWeight + ResultTurtles[m].Weight; end; PreMaxWeight := z; z := CurrentWeight - z; //Осталось проверить черепах от LocalIndex до z MinWeight := LocalIndex; MaxWeight := LocalIndex + z; for n := MinWeight to MaxWeight do begin //Теперь уже записываем черепашек по одной, начиная с тяжелых и выносливых // и каждый раз проверяем условия for m := Length(Turtles) - 1 downto 0 do if (not ResultTurtles[m].Used) and (Turtles[m].Weight = n) then begin ResultTurtles[m] := Turtles[m]; ResultTurtles[m].Used := True; for z := 0 to Length(Turtles) - 1 do if not InCondition then begin ResultTurtles[m].Used := False; Break; end; end; end; //Ну и последнее //Возможно, что черепашка с самой высокой грузоподъемностью - не самая тяжелая, //а запас по массе еще небольшой остался. CurrentWeight := PreMaxWeight; for n := Length(Turtles) - 1 downto 0 do begin if ResultTurtles[n].Used then begin for m := 1 to ResultTurtles[n].Cargo - CurrentWeight do if Turtles[m+n].Cargo >= CurrentWeight then begin ResultTurtles[n+m] := Turtles[n+m]; ResultTurtles[n+m].Used := True; CurrentWeight := CurrentWeight + ResultTurtles[n+m].Weight; end; Break; end; end; end;

> Alx2 © (04.06.10 22:32) [88]
> Ощущение, что мы совпали полностью (после твоего заамечания про сортировку ) :)

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

Три нижних черепашки в первом тесте у меня другие:
...........
03 91
03 93
05 92
03 96

Второй тест дал полностью совпадающий результат.

> ZeroDivide © (05.06.10 00:57) [93]

Правильно ли я понимаю, что у тебя всегда получается решение,
в котором черепашки упорядочены по силе панциря?

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

>
> Правильно ли я понимаю, что у тебя всегда получается решение,
>
> в котором черепашки упорядочены по силе панциря?
>

Да, черепашки всегда будут упорядочены по силе панциря, если построить ряд из самых "эффективных" черепашек. Можно даже логически объяснить, что для построения максимальной цепочки необходимо, чтобы n-1 черепаха была равна или больше по грузоподъемности чем - n-ая.

Вот самый эффективный ряд, для первого теста:
1: 4 - 3 - 0
2: 2 - 4 - 4
3: 2 - 7 - 6
4: 3 - 19 - 8
5: 4 - 23 - 11
6: 2 - 24 - 15
7: 4 - 27 - 17
8: 2 - 30 - 21
9: 4 - 30 - 23
10: 1 - 35 - 27
11: 5 - 36 - 28
12: 3 - 41 - 33
13: 2 - 42 - 36
14: 6 - 47 - 38
15: 5 - 48 - 44
16: 1 - 57 - 49
17: 2 - 62 - 50
18: 5 - 63 - 52
19: 3 - 70 - 57
20: 5 - 70 - 60
21: 1 - 71 - 65
22: 5 - 74 - 66
23: 5 - 85 - 71
24: 7 - 89 - 76
25: 3 - 91 - 83
26: 5 - 92 - 86
27: 3 - 93 - 91
28: 3 - 96 - 94

Т.е. максимальеная цепочка: 28,
Максимальный запас, максимальной цепочки: 96-94: 2

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

> ZeroDivide © (05.06.10 12:14) [96]
> Да, черепашки всегда будут упорядочены по силе панциря,
> если построить ряд из самых "эффективных" черепашек.

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

> Можно даже логически объяснить, что для построения максимальной
> цепочки необходимо, чтобы n-1 черепаха была равна или больше по
> грузоподъемности чем - n-ая.

В том то и дело, что не необходимо.
И у Alx2, и у меня черепахи упорядочены иначе.

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

Интересно сравнить с DP.

ZeroDivide © (05.06.10 0:57) [93]

Во многих случаях дает оптимальное решение. Очень быстро дает. Но я нашел контрпример. Вот тест:

----------
{1 1} {2 2} {3 3} {4 4} {5 5} {6 6} {7 7} {8 8} {9 9} {10 10} {11 11} {12 12} {13 13} {14 14} {15 15} {16 16} {17 17} {18 18} {19 19} {20 20} {21 21} {22 22} {23 23} {24 24} {25 25} {26 26} {27 27} {28 28} {29 29} {30 30} {31 31} {32 32} {33 33} {34 34} {35 35} {36 36} {37 37} {38 38} {39 39} {40 40} {41 41} {42 42} {43 43} {44 44} {45 45} {46 46} {47 47} {48 48} {49 49} {50 50} {51 51} {52 52} {53 53} {54 54} {55 55} {56 56} {57 57} {58 58} {59 59} {60 60} {61 61} {62 62} {63 63} {64 64} {65 65} {66 66} {67 67} {68 68} {69 69} {70 70} {71 71} {72 72} {73 73} {74 74} {75 75} {76 76} {77 77} {78 78} {79 79} {80 80} {81 81} {82 82} {83 83} {84 84} {85 85} {86 86} {87 87} {88 88} {89 89} {90 90} {91 91} {92 92} {93 93} {94 94} {95 95} {96 96} {97 97} {98 98} {99 99} {100 100}

Длина столба: 8
Решение:
{96 96} {48 48} {24 24} {12 12} {6 6} {3 3} {2 2} {1 1}

---------------

А вот что дает твой алгоритм:

Длина столба: 5
Решение:
{7 7} {6 6} {3 3} {2 2} {1 1}

Sha © (05.06.10 2:45) [94]
Три нижних черепашки в первом тесте у меня другие:

Видимо, из-за того, что решений много. А алгоритм их обхода у нас немного отличается в части "куды бечь". Имхо, отсюда разница в деталях.

ZeroDivide © (05.06.10 0:57) [93]
На этом тесте у тебя AV.:
{1 1000} {1 1000} {1 1000} {1 1000} {1 1000} {1 1000} {1 1000} {1 1000} {1 1000} {1 1000} {2000 1} {2000 1} {2000 1} {2000 1} {2000 1} {2000 1} {2000 1} {2000 1} {2000 1} {2000 1}

>ZeroDivide © (05.06.10 0:57) [93]

Вот тест, который показывает, что [96] не выолняется
Я про этот фрагмент:
"Можно даже логически объяснить, что для построения максимальной цепочки необходимо, чтобы n-1 черепаха была равна или больше по грузоподъемности чем - n-ая."

Итак, тест:
{1 20} {1 20} {1 20} {1 20} {1 20} {1 20} {1 20} {1 20} {1 20} {1 20} {100 10} {100 10} {100 10} {100 10} {100 10} {100 10} {100 10} {100 10} {100 10} {100 10}

Длина столба: 11
Решение:
{100 10} {1 20} {1 20} {1 20} {1 20} {1 20} {1 20} {1 20} {1 20} {1 20} {1 20}

Здесь видно, что в основании столба лежит жирная, но хиленькая черепаха. Ее больше никуда нельза сунуть, не ухудшив решение.

> Длина столба: 8
> Решение:
> {96 96} {48 48} {24 24} {12 12} {6 6} {3 3} {2 2} {1 1}
>
> ---------------
>
> А вот что дает твой алгоритм:
>
> Длина столба: 5
> Решение:
> {7 7} {6 6} {3 3} {2 2} {1 1}

Я понял :) Проверю, думаю исправить нужно..., но не логику поиска а, скорее, реализацию.

> Здесь видно, что в основании столба лежит жирная, но хиленькая
> черепаха. Ее больше никуда нельза сунуть, не ухудшив решение.
>

Вот блин.... Мой алгоритм, быстро даст результат на рандомайзе большого количества... тут же, частные случаи... буду думать...

Задачка становится все интереснее... :)

Добавил функцию вычисления высоты стопки аналогично [85]
и вывод получающейся матрицы ДП, для желающих поэкспериментировать.
Плюс соединил куски, чтобы все было вместе.
(* Имеется набор черепах. Каждая черепаха обладает известной массой и известной грузоподъемностью (заданной в единицах массы). Требуется найти максимальную высоту столба из черепах (поставленных друг на друга). *) type PTurtle= ^TTurtle; TTurtle= record w: integer; //weight c: integer; //carrying p: integer; //previous b: integer; //best end; var a: array of TTurtle; best, first: integer; //Matrix[i,m] содержит высоту стопки весом m или меньше черепах с номерами i или больше //Matrix[i,m]:=Matrix[i+1,m], если i-тая черепаха не входит в стопку массой m //Matrix[i,m]:=Matrix[i+1,m-a[i].w]+1, если входит Matrix: array of array of integer; procedure TurtleLoad; var i: integer; begin; SetLength(a,100); Randomize; for i:=0 to Length(a)-1 do begin; a[i].w:=Random(29)+1; a[i].c:=Random(29)+1; end; end; //В оптимальной стопке черепашки всегда будут расположены в порядке, //соответствующем их силе ног = собственный вес + сила панциря //Доказательство см. в обсуждении задачи на delphimaster.ru function LegsAreStronger(p1, p2: PTurtle): boolean; var m1, m2: integer; begin; m1:=p1.c + p1.w; m2:=p2.c + p2.w; Result:=(m1>m2) or (m1=m2) and (p1.c<p2.c); end; procedure TurtleSort; var t: TTurtle; i: integer; done: boolean; begin; repeat; done:=true; for i:=0 to Length(a)-2 do if LegsAreStronger(@a[i+1],@a[i]) then begin; t:=a[i]; a[i]:=a[i+1]; a[i+1]:=t; done:=false; end; until done; end; procedure TurtleSolution(previous, count: integer); var weight, i, j: integer; begin; for i:=previous+1 to Length(a)-1 do begin; j:=i; weight:=0; a[i].p:=previous; repeat; weight:=weight+a[j].w; j:=a[j].p; until (j<0) or (weight>a[j].c); if j<0 then TurtleSolution(i, count+1); end; if best<count then begin; best:=count; first:=previous; j:=first; repeat; a[j].b:=a[j].p; j:=a[j].p; until j<0; end; end; procedure TForm1.TurtlePrintSolution; const validation: array[boolean] of string= ("invalid", "valid"); var i, j, total: integer; valid: boolean; begin; Memo1.Lines.Clear; Memo1.Lines.Add(" weight carrying"); Memo1.Lines.Add("-------------------------------"); for i:=0 to Length(a)-1 do Memo1.Lines.Add(Format("%.2d %.2d %.2d",[i, a[i].w, a[i].c])); Memo2.Lines.Clear; Memo2.Lines.Add(Format("count = %d",[best])); Memo2.Lines.Add(" weight carrying"); Memo2.Lines.Add("-------------------------------"); i:=first; total:=0; valid:=true; while i>=0 do begin; Memo2.Lines.Add(Format("%.2d %.2d %.2d",[i, a[i].w, a[i].c])); valid:=valid and (total<=a[i].c); total:=total+a[i].w; i:=a[i].b; end; Memo2.Lines.Add("-------------------------------"); Memo2.Lines.Add(Format("total = %d, %s",[total,validation[valid]])); if Length(Matrix)>0 then begin; StringGrid1.DefaultColWidth:=24; StringGrid1.DefaultRowHeight:=18; StringGrid1.ColCount:=Length(Matrix)+1; StringGrid1.RowCount:=Length(Matrix[0])+1; for j:=1 to StringGrid1.RowCount-1 do StringGrid1.Cells[0,j]:=IntToStr(j); for i:=0 to Length(Matrix)-1 do begin; StringGrid1.Cols[i+1].Clear; StringGrid1.Cells[i+1,0]:=IntToStr(i); for j:=1 to Length(Matrix[i])-1 do StringGrid1.Cells[i+1,j]:=IntToStr(Matrix[i,j]); end; end; end; procedure TurtleMatrixDP; var i, m, m1, m2, m3, count: integer; begin; SetLength(Matrix,Length(a)); i:=Length(a)-1; m:=a[i].w; SetLength(Matrix[i],m+1); Matrix[i,m]:=1; while m>0 do begin; dec(m); Matrix[i,m]:=0; end; dec(i); while i>=0 do begin; m1:=Length(Matrix[i+1])-1; m:=a[i].c+a[i].w; SetLength(Matrix[i], m+1); while m>=0 do begin; m3:=m; if m3>m1 then m3:=m1; count:=Matrix[i+1,m3]; m2:=m-a[i].w; m3:=m2; if m3>m1 then m3:=m1; if (m2>=0) and (m2<=a[i].c) and (count<=Matrix[i+1,m3]) then count:=Matrix[i+1,m3]+1; Matrix[i,m]:=count; dec(m); end; dec(i); end; end; procedure TurtleSolutionDP; var i, imax, m, m1, count: integer; begin; first:=-1; best:=0; m:=Length(Matrix[0])-1; imax:=Length(Matrix)-1; for i:=0 to imax do begin; count:=Matrix[i,m]; if count=0 then break; while (m>0) and (count=Matrix[i,m-1]) do dec(m); if i<imax then begin; m1:=Length(Matrix[i+1])-1; if m1>m then m1:=m; if Matrix[i+1,m1]=count then begin; m:=m1; continue; end; end; inc(best); a[i].b:=first; first:=i; m:=m-a[i].w; end; end; function TurtleCountDP: integer; var counts: array[0..1] of array of integer; i, m, mmax, mcolumn, count, old: integer; begin; SetLength(counts[0],a[0].w + a[0].c + 1); SetLength(counts[1],a[0].w + a[0].c + 1); old:=0; i:=Length(a)-1; mmax:=a[i].w; counts[old,mmax]:=1; for m:=0 to mmax-1 do counts[old,m]:=0; dec(i); while i>=0 do begin; count:=counts[old,mmax]; m:=a[i].w + a[i].c; while mmax<m do begin; inc(mmax); counts[old,mmax]:=count; end; while m>=0 do begin; count:=counts[old,m]; mcolumn:=m - a[i].w; if (mcolumn>=0) and (mcolumn<=a[i].c) and (count<=counts[old,mcolumn]) then count:=counts[old,mcolumn] + 1; counts[1-old,m]:=count; dec(m); end; old:=1-old; dec(i); end; Result:=counts[old,mmax]; end; procedure TForm1.bLoadAndSortClick(Sender: TObject); begin; TurtleLoad; TurtleSort; end; procedure TForm1.bRecursionClick(Sender: TObject); begin; first:=-1; best:=0; TurtleSolution(-1, 0); TurtlePrintSolution; end; procedure TForm1.bDPSolutionClick(Sender: TObject); begin; TurtleMatrixDP; TurtleSolutionDP; TurtlePrintSolution; end; procedure TForm1.bDPCountClick(Sender: TObject); begin; Memo2.Lines.Clear; Memo2.Lines.Add(Format("count = %d",[TurtleCountDP])); end;

Sha © (06.06.10 2:31) [104]
//В оптимальной стопке черепашки всегда будут расположены в порядке,
//соответствующем их силе ног = собственный вес + сила панциря

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

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

Сейчас фоном рассматриваю вариант упорядочивания (по грузоподъемности) от ZeroDivide. Исключений для положительных масс действительно, мало. Но на "антигравитационных" черепах не работает. :)

Alx2 © (06.06.10 16:12) [105]

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

А т.к. мы заранее располагаем их по силе ног,
и перебираем все допустимые подпоследовательности,
то мы не потеряем ни одного оптимального решения.

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

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