maximale Teilmenge von ganzen Zahlen, die von k

Question

Diese nicht gleichmäßig teilbar sind, ist eine Praxis Problem, das ich bin Lösung:

eine Menge S von verschiedenen ganzen Zahlen gegeben, die Größe einer maximalen Teilmenge S‘von S drucken wobei die Summe aus alle 2 Zahlen in S 'sind nicht gleichmäßig durch k teilbar.

Mein Ansatz war, das Problem auf die Teilmenge zu begrenzen S[0...i] wobei 0 < i < = n-1 und die Länge der maximalen Teilmenge für dieses Teilproblem bestimmen, erweitern Sie dann die Subproblem von 1. Ich weiß, dass es ein anderer Ansatz ist zu diesem Problem, aber ich bin verwirrt, warum meine Lösung nicht funktioniert.

ex) für n = 10, k = 5 und S = [770528134, 663501748, 384261537, 800309024, 103668401, 538539662, 385488901, 101262949, 557792122, 46058493]

dp = [0 for _ in range(n)] 
dp[0] = 1 
for i in range(1, n): 
    flag = 0 
    for j in range(i): 
     if s[j] == "#": 
      pass 
     elif (not s[j] == "#") and (s[j] + s[i])%k==0: 
      dp[i] = dp[i-1] 
      flag = 1 
      s[i] = "#" 
      break 
    if not flag == 1: 
     dp[i] = dp[i-1] + 1 
print dp[-1] 

Der Ausgang 6 aber meine Funktion druckt 5 sein sollte. Was ich versuche zu tun ist von j=0 zu i iterieren und prüfen, ob für irgendwelche j < i wenn (s[j] + s[i])%k==0. Wenn dies der Fall ist, dann wäre die Betrachtung von s[i] in S 'fehlerhaft, stattdessen markieren Sie s[i] mit einer #, um anzuzeigen, dass es nicht in S' ist.

Answer 1

Ihr Mangel an Kommentaren und erklärenden Namen macht Ihren Code sehr schwer zu folgen, also verstehe ich es nicht. (Ihr Beispiel, das eine Liste verwendet, wenn Sie von Mengen sprechen, und die Verwendung von s und S für Ihr "set", hilft nicht.) Die Grundidee Ihres Algorithmus ist jedoch fehlerhaft: Dieses Problem für eine gegebene Menge kann nicht sein gelöst, indem die Lösung für eine richtige Teilmenge erweitert wird.

Nehmen Sie zum Beispiel k=3, setzen Sie S=[1,4,2,5,8]. Für die ersten drei Elemente [1,4,2] ist die Lösung [1,4]. Für die ersten vier Elemente [1,4,2,5] ist die Lösung entweder [1,4] oder [2,5]. Für den gesamten Satz ist die Lösung [2,5,8]. Sie sehen, dass es keinen "Weg" von der Lösung von den ersten drei Elementen durch die ersten fünf gibt: Sie müssen entweder bei den ersten vier oder dem gesamten Satz "neu starten".

Eine Lösung, die funktioniert, unterteilt die gesamte Menge S in Äquivalenzklassen, wobei die Elemente in jeder Klasse den gleichen Rest haben, wenn sie durch k geteilt werden. Die Untersuchung dieser Äquivalenzklassen ergibt das Endergebnis. Lassen Sie mich wissen, wenn Sie weitere Informationen benötigen. Beachten Sie, dass Sie klar entscheiden müssen, ob any 2 numbers in S' irgendwelche 2 distinkten Zahlen in S 'bedeutet: das ändert, was Sie bei einer oder zwei der Äquivalenzklassen tun.