203
&$! > = (5! = 120 =
) 5 =:
{1, ...}, {2, ...},..., {n, ...}. @ $! -
=, 2, $ -
!< = $ V 2:
{2, 1, 3, 4, 5}, {2, 1, 3, 5, 4}, {2, 1, 4, 3, 5}, {2, 1, 4, 5, 3}, {2, 1, 5, 3, 4},
{2, 1, 5, 4, 3},
{2, 3, 1, 4, 5}, {2, 3, 1, 5, 4}, {2, 3, 4, 1, 5}, {2, 3, 4, 5, 1}, {2, 3, 5, 1, 4},
{2, 3, 5, 4, 1},
{2, 4, 1, 3, 5}, {2, 4, 1, 5, 3}, {2, 4, 3, 1, 5}, {2, 4, 3, 5, 1}, {2, 4, 5, 1, 3},
{2, 4, 5, 3, 1},
{2, 5, 1, 3, 4}, {2, 5, 1, 4, 3}, {2, 5, 3, 1, 4}, {2, 5, 3, 4, 1}, {2, 5, 4, 1, 3},
{2, 5, 4, 3, 1}.
* = $ $ " =.
C" =< =,
$ =< $ $ <
i
, i = 1, 2, 3, 4, 5.
@ i = 1:
A (
1
) = A (
o
) +a
1
= 0 + 2 = 2;
B (
1
) = max (A (
1
), B (
0
)) + b
1
= max (2,0) + 3 = 5
C (
1
) = max (B (
1
), C (0)) + c
1
= max (5,0) + 4 = 5 + 4 = 9;
A1
= A(
1)
+Wa
i
+ min (b
i
+ c
i
)= 2 + 12 + 3 = 17, i 1;
B1
= B(
1)
+Wb
i
+ min c
i
= 5 + 12 + 2 = 19, i 1;
C1
= C(
1
) +Wc
i
= 9 +10 = 19, i 1.
?
1
= max (17, 19, 19) = 19.
% = , # # $$ -
V 1, $$ " =
19 .
@ i = 2:
A (
1
) = A (
o
) + a
2
= 0 + 5 = 5;
B (
1
) = max (A (
1
), B (
0
)) + b
2
= max (5,0) + 2 = 7
C (
1
) = max (B (
1
), C (
0
)) + c
2
= max (7,0) + 4 = 7 + 4 = 11;
A1
= A (
1
) + Wa
i
+ min (b
i
+ c
i
) = 5 +9 + 3 =17, i 1;
B1
= B (
1
) + Wb
i
+ min c
i
=
7 + 13 + 2 = 22, i 1;
C1
= C (
1
) + Wc
i
= 11 + 10 = 21, i 1.
?
2
= max (17, 22, 21) = 22.
% = , # # $$
V 2, $$ " = 22 -
.
* =! " =:
i = 3: A(
1
) = 1, B(
1
) = 2, C(
1
) = 4,
A1
= 20,
B1
= 18,
C1
= 16,
3
= 20;
i = 4: A(
1
) = 3, B(
1
) = 7, C(
1
) = 9,
A1
= 17,
B1
= 20,
C1
= 21,
4
= 21;
i = 5: A(
1
) = 3, B(
1
) = 8, C(
1
) = 10,
A1
= 20,
B1
= 22,
C1
= 22,
5
= 22.