Subset-sum-rekursiv in Python
Ich bin glücklich, etwas Hilfe zu bekommen.
Ich habe Folgendes problem:
Ich eine Liste von zahlen seq
- und eine Ziel-Nummer und schreiben brauche ich 2 Dinge:
-
Eine rekursive Lösung gibt
True
wenn es eine Summe einer Teilfolge, die gleich der Zielnummer undFalse
sonst.
Beispiel:subset_sum([-1,1,5,4],0) # True subset_sum([-1,1,5,4],-3) # False
-
Zweitens schreiben brauche ich eine Lösung die mit dem, was ich schrieb in der früheren Lösung
aber jetzt mit memoization, verwendet ein Wörterbuch, in dem die Tasten sind Tupeln:
(len(seq),target)
Für die Nummer 1 das ist, was ich habe, so weit:
def subset_sum(seq, target):
if target == 0:
return True
if seq[0] == target:
return True
if len(seq) > 1:
return subset_sum(seq[1:],target-seq[0]) or subset_sum(seq[1:],target)
return False
Nicht sicher, ob ich es richtig so, wenn ich könnte einige input-ich werde dankbar sein.
Für Nummer 2:
def subset_sum_mem(seq, target, mem=None ):
if not mem:
mem = {}
key=(len(seq),target)
if key not in mem:
if target == 0 or seq[0]==target:
mem[key] = True
if len(seq)>1:
mem[key] = subset_sum_mem(seq[1:],target-seq[0],mem) or subset_sum_mem(seq[1:],target,mem)
mem[key] = False
return mem[key]
Komme ich nicht an die memoization, geben Sie mir die richtige Antwort, so wäre ich froh um einige Hinweise hier.
Dank für alle die bereit sind zu helfen!
- Irgendeinem Grund sind Sie nicht einfach nur mit
@memoize
? - Wahrscheinlich, weil es die Hausaufgaben 😉
- Kennzeichnen Sie bitte als Hausaufgabe, wenn dies in der Tat Hausaufgaben. Werden die Menschen immer noch Hilfe. Es ist gut in form und kann Menschen helfen zu verstehen, wo Sie herkommen.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Nur als Referenz, hier ist eine Lösung mit dynamischer Programmierung:
def positive_negative_sums(seq): return sum(e for e in seq if e >= 0), sum(e for e in seq if e < 0)
Dies ist, wie ich schreiben
subset_sum
:Klappte es auf, ein paar Beispiele:
Um ehrlich zu sein, würde ich nicht wissen, wie memoize es.
Alt Edit: habe ich entfernt, die Lösung mit
any()
weil nach einigen tests fand ich heraus, dass langsamer zu sein!Update: Nur aus Neugier könnten Sie auch
itertools.Kombinationen
:Diese können es besser, dass die dynamische Programmierung Ansatz in einigen Fällen, aber in anderen ist er hängen (es ist sowieso besser, dann ist der rekursive Ansatz).
subset_sum = lambda seq, target: (target == 0) or any(subset_sum(seq[:i] + seq[i+1:], target - v) for i, v in enumerate(seq))
für uns Masochisten 😉 Memoization ist eigentlich trivial Wörterbuchs in diesem Fall. Schöne Lösung!Habe ich diese modifizierte code:
Können Sie einige Testfälle dies nicht funktioniert?
[]
als return-Wert an einem Punkt in meiner Experimente, so warf ichright
um ein bool. Ich kann jetzt nicht kommen mit einem Fall, wo es benötigt wird.bool(right)
zuright
und versuchen:subset_sum([2], 1)
undsubset_sum_mem([2], 1)
.