Ich habe also eine gegebene Menge C von n positiven ganzen Zahlen(c_1, ..., c_n). Die Aufgabe besteht darin, zwei Teilmengen A und B von C zu finden, wobei A nur positive Zahlen enthält und B nur die Negative der Zahlen in C enthält. Die Summe der beiden Teilmengen A und B sollte sich dann zu einer Zahl d summieren (d ist immer positiv). Ich muss herausfinden, ob es zwei solcher Subsets gibt und wenn ja, welche Nummern sie enthalten.
For example: {3, 5, 6, 13, 24} // d = 12
=> solution: true: {5, 13} {-6}
Ich weiß, dass dies eine Variation der Teilmengensumme istProblem und ich habe einige Lösungen für ein ähnliches Problem gesehen (Teilmenge mit negativen Zahlen), aber ich muss das Problem mit dynamischer Programmierung lösen. Die meisten Lösungen, die ich gesehen habe, haben mit Rekursion gearbeitet, nicht mit DP.
Ich denke ich brauche einen 3D-Booleschen Tisch S (i, j, k) mitGröße (n * n * d). Aber wann ist S (i, j, k) wahr und wann falsch? Da ich immer alle Möglichkeiten zur Berechnung einer Summe anhand der k-Nummer prüfen muss, können sie sowohl positiv als auch negativ sein (Beispiel: Für 4 Zahlen {1,2,3,4} gibt es zwei Möglichkeiten, um eine Anordnung vorzunehmen sie: 1 + 2 + 3 + 4, 1 - 2 + 3 + 4, 1 - 2 - 3 + 4, ..., -1 + 2 - 3 - 4, 1 - 2 - 3 - 4)
Ist mein Denken richtig oder mache ich schon etwas falsch?
Antworten:
1 für die Antwort № 1Ein Ansatz ist die Verwendung des dynamischen Summenalgorithmus für die Programmierung der Teilmenge in einer Menge bestehend aus (c_1, c_2, ..., c_n, -c_1, -c_2, ..., - c_n).
Dies wird eine Untermenge finden, die sich zu d summiert (oder beweist, dass keines existiert).
Setzen Sie A für alle positiven Zahlen in der Untermenge und B für alle negativen Zahlen.
Möglicherweise möchten Sie auch alle Zahlen entfernen, die in A und B angezeigt werden (wenn Sie beispielsweise eine 3 in A und -3 in B haben, können Sie beide entfernen, ohne die Summe zu ändern.