Erkennen von Zahlenpaaren

[Neutral General]

Zitat von Namenloser:

Weiß nicht, ob ich deinen Code richtig verstehe, aber ich glaube, der findet nicht immer eine Lösung:

Probier mal

Code:

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ß.

Vorgabe ist dass die Summe beider Mengen gleich ist. Das ist bei deinem Beispiel nicht der Fall.

Ich nehme mir nacheinander jede Zahl aus der 2. Menge und suche aus der ersten Menge die größten Zahlen mit denen ich die Summe bilden kann.

16:
Größte Zahl <= 16 ist die 15 => 15 zur Summe hinzufügen und aus Menge1 entfernen, 1 ist übrig
Größte Zahl <= 1 ist die 1 => 1 zur Summe hinzufügen und aus Menge1 entfernen, 0 ist übrig => fertig

13:
Größte Zahl <= 13 ist die 7 => 7 zur Summe hinzufügen und aus Menge1 entfernen, 6 ist übrig
Größte Zahl <= 6 ist die 6 => 6 zur Summe hinzufügen und aus Menge1 entfernen, 0 ist übrig => fertig

usw.

[Namenloser]

Zitat von Neutral General:

Vorgabe ist dass die Summe beider Mengen gleich ist. Das ist bei deinem Beispiel nicht der Fall.

Hmm, aber ändert das was?

Code:

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.

[Neutral General]

Zitat von Namenloser:

Zitat von Neutral General:

Vorgabe ist dass die Summe beider Mengen gleich ist. Das ist bei deinem Beispiel nicht der Fall.

Hmm, aber ändert das was?

Code:

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.

Aber hier ist ja auch generell keine Lösung möglich oder?
Oder dürfen die Summen "mit zurücklegen" gebildet werden? Weil ansonsten fällt nach 16=5+5+6 der Rest so oder so flach.

[Namenloser]

Zitat von Neutral General:

Oder dürfen die Summen "mit zurücklegen" gebildet werden? Weil ansonsten fällt nach 16=5+5+6 der Rest so oder so flach.

Also ich habe das zumindest so verstanden. Aber auch, wenn man "Zurücklegen" nicht erlaubt, bezweifle ich, dass es immer geht. Z.B. bei:

Code:

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 gefunden, aber es würde mich doch wundern, wenn es keines gäbe.

[Neutral General]

Zitat von Namenloser:

Zitat von Neutral General:

Oder dürfen die Summen "mit zurücklegen" gebildet werden? Weil ansonsten fällt nach 16=5+5+6 der Rest so oder so flach.

Also ich habe das zumindest so verstanden. Aber auch, wenn man "Zurücklegen" nicht erlaubt, bezweifle ich, dass es immer geht. Z.B. bei:

Code:

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 gefunden, aber es würde mich doch wundern, wenn es keines gäbe.

Ja da hast du Recht. Aber mit absteigender Sortierung gehts wieder
Wie gesagt: Ich hab selbst keinen Beweis dass das immer so funktioniert. Und wenn es "mit zurücklegen" ist, dann ist mein Code eh an der Aufgabenstellung vorbei

[Namenloser]

Habe doch noch eins gefunden:

Code:

List<int> MengeA = new List<int>(new int[] { 13, 10, 4 });
List<int> MengeB = new List<int>(new int[] { 14, 13 });

Oder auch

Code:

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.