Maximierung der arithmetischen Ausdruck

Question

ich will, ist der Ausdruck 5-8+7*4-8+9 und Antwort maximieren 200 nach auf diese Weise aufzuteilen (5 − ((8 + 7) × (4 − (8 + 9)))).

Es kann durch Verwendung Matrix-chain multiplication Algorithmus gelöst werden. Es gibt richtige Antwort, wenn Ausdruck nur '+' hat und '*' Operator

Let's take expression 5+2*4 
    1 2 3 
    1 5 7 28 
    2 - 2 8 
    3 - - 4 

Es ist eine 3x3-Matrix, in der (1,1) 5, (2,2) 2 und (3,3) 4 und wenn ich will M [1] [2] oder M [1] [3] dann

M [1] [2] = M [1] [1] o M wissen [ 2] [2]

M [1] [3] = max (M [1] [1] o M [2] [3], M [1] [2] o M [3] [3])

kann mir jemand helfen, die richtige Methode im Falle von '-' zu finden.

Answer 1

Nicht sicher, ob es mit Ihrem Algorithmus gelöst werden kann, aber hier wäre, wie ich es gelöst hätte.

Angenommen, Sie müssen einige Ausdrücke vereinfachen: a # b # C# d # e, wobei # eine Operation ist (# kann unterschiedlich sein). Ich würde es mit Rekursion (und Memoisierung) nähern. Im ersten Schritt der Rekursion werde ich versuchen, Klammern an jeder möglichen Position einzusetzen und Expression nach diesem Ausdruck zu berechnen:

• (a # b) # C# d # e = X # C# d # e
• a # (b # c) # d # e = a # Y # d # e
• a # b # (C# d) # e = a # b # Z # e
• a # b # C# (d # e) = a # b # C# V

Sie haben also im Grunde nur 5 Operatorausdrücke auf eine Menge von 4 Operatorausdrücken reduziert. Memoization ist hilfreich, wenn 2 Ausdrucke gleich sind. Sie beenden Ihre Rekursion, wenn es nur eine Zahl gibt (in diesem Fall vergleichen Sie sie mit Maximum und Maximum aktualisieren).

Beachten Sie, dass Sie für Ihren Ausdruck mit 5 Operatoren nicht einmal Memoization benötigen.