Текущий архив: 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.058 c
