44 lines
792 B
Plaintext
44 lines
792 B
Plaintext
ClearAll[optim, aux]
|
|
optim[a_List] := Module[{u, v, n, c, r, s},
|
|
n = Length[a] - 1;
|
|
u = ConstantArray[0, {n, n}];
|
|
v = ConstantArray[\[Infinity], {n, n}];
|
|
u[[All, 1]] = -1;
|
|
v[[All, 1]] = 0;
|
|
Do[
|
|
Do[
|
|
Do[
|
|
c =
|
|
v[[i, k]] + v[[i + k, j - k]] + a[[i]] a[[i + k]] a[[i + j]];
|
|
If[c < v[[i, j]],
|
|
u[[i, j]] = k;
|
|
v[[i, j]] = c;
|
|
]
|
|
,
|
|
{k, 1, j - 1}
|
|
]
|
|
,
|
|
{i, 1, n - j + 1}
|
|
]
|
|
,
|
|
{j, 2, n}
|
|
];
|
|
r = v[[1, n]];
|
|
s = aux[u, 1, n];
|
|
{r, s}
|
|
]
|
|
aux[u_, i_, j_] := Module[{k},
|
|
k = u[[i, j]];
|
|
If[k < 0,
|
|
i
|
|
,
|
|
Inactive[Times][aux[u, i, k], aux[u, i + k, j - k]]
|
|
]
|
|
]
|
|
{r, s} = optim[{1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2}];
|
|
r
|
|
s
|
|
{r, s} = optim[{1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10}];
|
|
r
|
|
s
|