() [5] . , . .
. - .
, .1.1. , , . , , x1. , , . . , .
: , , , .. . , . , , .
, , . , 100 , 20 . - 80 , 20. , 20 , , 10 , , .
. , A B C, D E: ACDEB, ADECB, AEDCB .. . , B A, , C, D E.
:
, .
( ) .
, , .
|
|
, .
, . .
.
, n, bi, ci, B. C(X) = Scixi Sbixi £ B.
v(k,y) ( ) , C(X) , Sbixi £ y xi i > k 0. v(k,y) k, 0 £ k £ n, y, 0 £ y £ B. , . v(n,B), .
v(k,y) :
v(1,y) = entier(y/b1) × ci;
v(k,y) = max(ckxk + v(k-1, y - bkxk)) k > 1.
xk , 0 £ xk £ entier(y/bk), entier, , .
. , , y.
. y k- 0 entier(y/bk). xk, k- ckxk, bkxk, 1 k-1 y - bkxk . ? v, , v(k-1, y - bkxk)! xk k- .
, v , . .
, v(k,y) k.
: n = 4, bi = (5, 7, 9, 4), ci = (9, 15, 19, 8), B = 20.
, . xk, : (ck/bk) , . , , 15/7, 20 300 / 7 42.86. , , 42.
|
|
v(k,y) . , xk, . .1.11.
1.11
k = 1 | k = 2 | k = 3 | k = 4 | |||||
y | x1 | v(1,y) | x2 | v(2,y) | x3 | v(3,y) | x4 | v(4,y) |
. 1.11
k = 1 | k = 2 | k = 3 | k = 4 | |||||
y | x1 | v(1,y) | x2 | v(2,y) | x3 | v(3,y) | x4 | v(4,y) |
0 (3) | ||||||||
0 (1) | ||||||||
0 (3) | ||||||||
. .
k = 2, y = 7 entier(y/bk) = entier(7/7) = 1, xk 0 1. :
v(2, 7) = max((15×0 + v(1, 77×0)), (15×1 + v(1, 77×1))) =
= max((0+v(1,7)), (15+v(1,0))) = max(0+9, 15+0) = 15.
k = 4, y = 12 entier(y/bk) = entier(12/4) = 3, xk 0, 1, 2 3. :
v(4, 12) = max((8×0 + v(3, 124×0)), (8×1 + v(3, 124×1),
(8×2 + v(3, 124×2), (8×3 + v(3, 124×3))) =
= max((0+v(3,12)), (8+v(3,8)), (16+v(3,4)), (24+v(3,0))) =
= max(0+24, 8+15, 16+0, 24+0) = 24.
xk, .1.11. , .
.
. k- bk, ck v(k-1, y) . , , , .
, k = 4 , , , 4 20 42 . , !
, , .. xk, . .
|
|
, v(4,20) = 42 x4 = 1. , 20 b4x4 = 16 . , v(3,16) = 34 x3 = 1. 16 b3x3 = 7 . v(2,7) = 15 x2 = 1. 7 b2x2 = 0 , , , x1 = 0. , X = (0, 1, 1, 1).
, : n B. n, B+1. , , B. , T(n,B) = O(nB2).