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:

  1. Eine rekursive Lösung gibt True wenn es eine Summe einer Teilfolge, die gleich der Zielnummer und False sonst.
    Beispiel:

    subset_sum([-1,1,5,4],0)   # True
    subset_sum([-1,1,5,4],-3)  # False
  2. 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.
InformationsquelleAutor user1123417 | 2012-01-26
Schreibe einen Kommentar