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

← →
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 :)

не помню уже

aka (04.06.10 13:57) [66]

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

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

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

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

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

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

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

//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 © (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 черепашек.

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