Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2010.08.27;
Скачать: CL | DM;

Вниз

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

 
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}


 
Alx2 ©   (2010-06-05 15:42) [99]

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


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


 
Alx2 ©   (2010-06-05 16:56) [100]

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}


 
Alx2 ©   (2010-06-05 17:04) [101]

>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}

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


 
ZeroDivide ©   (2010-06-05 21:06) [102]


> Длина столба: 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}


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


 
ZeroDivide ©   (2010-06-05 21:08) [103]


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


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

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


 
Sha ©   (2010-06-06 02:31) [104]

Добавил функцию вычисления высоты стопки аналогично [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;


 
Alx2 ©   (2010-06-06 16:12) [105]

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


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

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

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


 
Sha ©   (2010-06-06 16:24) [106]

Alx2 ©   (06.06.10 16:12) [105]

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

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

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



Страницы: 1 2 3 вся ветка

Текущий архив: 2010.08.27;
Скачать: CL | DM;

Наверх




Память: 0.71 MB
Время: 0.135 c
6-1219075279
ocean
2008-08-18 20:01
2010.08.27
IdSmtp headers


15-1272054585
@!!ex
2010-04-24 00:29
2010.08.27
Вопрос по Inno Setup. Как обновить файл?


2-1266325693
Rail
2010-02-16 16:08
2010.08.27
как правильно указать путь к бд


2-1267340699
Officeman
2010-02-28 10:04
2010.08.27
как задать текст для имени Tclass edit1


15-1263677426
Юрий
2010-01-17 00:30
2010.08.27
С днем рождения ! 17 января 2010 воскресенье