Forum: Algorithmen, Datenstrukturen und Klassendesign
by Namenloser,
9. Okt 2015
Weiß nicht ganz, was du mir damit sagen willst. Falls du nur meinst, dass es auch andere Lösungen als Backtracking gibt: Weiß ich, meine verwendet auch kein Backtracking. Aber von Neutral Generals Ansatz (der ja nicht ganz funktioniert) ausgehend wäre Backtracking der nächste logische Schritt.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Namenloser,
9. Okt 2015
Habe doch noch eins gefunden:
List<int> MengeA = new List<int>(new int { 13, 10, 4 });
List<int> MengeB = new List<int>(new int { 14, 13 });
Oder auch
List<int> MengeA = new List<int>(new int { 13, 10, 4, 1 });
List<int> MengeB = new List<int>(new int { 14, 13, 1 });
Also ohne Backtracking wird es nicht gehen.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Namenloser,
9. Okt 2015
Also ich habe das zumindest so verstanden. Aber auch, wenn man "Zurücklegen" nicht erlaubt, bezweifle ich, dass es immer geht. Z.B. bei:
List<int> MengeA = new List<int>(new int { 5, 5, 5, 6, 15 });
List<int> MengeB = new List<int>(new int { 16, 20 });
Gut, da könnte man jetzt vielleicht sagen, MengeB muss auch absteigend sortiert sein. Habe ich jetzt zugegeben noch kein Gegenbeispiel für...
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Namenloser,
9. Okt 2015
Hmm, aber ändert das was?
List<int> MengeA = new List<int>(new int { 5, 5, 6, 15 });
List<int> MengeB = new List<int>(new int { 16, 5, 5, 5});
Hier sind die Summen gleich, die Lösung für die 16 wird meines Erachtens aber trotzdem nicht gefunden.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Namenloser,
9. Okt 2015
Weiß nicht, ob ich deinen Code richtig verstehe, aber ich glaube, der findet nicht immer eine Lösung:
Probier mal
List<int> MengeA = new List<int>(new int { 5, 5, 6, 15 });
List<int> MengeB = new List<int>(new int { 16 });
Ist aber eine gängige, schnelle Näherungslösung für das Rucksackproblem, soweit ich weiß.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Namenloser,
9. Okt 2015
Ich hätte es eher als Rucksackproblem identifiziert, wobei es ja letztlich auf dasselbe herausläuft: Beide sind NP-vollständig.
Mein Lösungsansatz ist ausgehend von dieser Idee: Mal angenommen, es gäbe nur Kombinationen der Länge 2. Dann wäre es ja einfach: Man subtrahiert einfach alle Zahlen aus Menge1 von allen Zahlen aus Menge2. Dann muss man nur noch prüfen, welche dieser Differenzen auch...
