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

← →
Sha © (2010-06-04 18:18) [80]

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

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

← →
Sha © (2010-06-04 18:40) [81]

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

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

← →
ZeroDivide © (2010-06-04 21:00) [82]

> 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

← →
ZeroDivide © (2010-06-04 21:02) [83]

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

← →
Alx2 © (2010-06-04 22:26) [84]

Sha © (04.06.10 18:40) [81]

Ну вот. А я не увидел :)

← →
Alx2 © (2010-06-04 22:27) [85]

Вот мой вариант (сорри за 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; }

← →
Alx2 © (2010-06-04 22:29) [86]

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

← →
Alx2 © (2010-06-04 22:29) [87]

ZeroDivide © (04.06.10 21:00) [82]

А код можно позырить? :)

← →
Alx2 © (2010-06-04 22:32) [88]

Sha © (04.06.10 18:18) [80]

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

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

← →
Sha © (2010-06-04 22:59) [89]

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

Да.

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

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

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

← →
Alx2 © (2010-06-04 23:02) [90]

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;

← →
Alx2 © (2010-06-04 23:13) [91]

Sha © (04.06.10 22:59) [89]

Задачу зато рассмотрели, как минимум, двусторонне :)

← →
Putnik © (2010-06-04 23:38) [92]

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

← →
ZeroDivide © (2010-06-05 00:57) [93]

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;

← →
Sha © (2010-06-05 02:45) [94]

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

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

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

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

← →
Sha © (2010-06-05 10:22) [95]

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

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

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

← →
ZeroDivide © (2010-06-05 12:14) [96]

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

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

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

← →
Sha © (2010-06-05 12:50) [97]

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

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

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

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

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

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

← →
Alx2 © (2010-06-05 15:38) [98]

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]

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

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

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

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