Erkennen von Zahlenpaaren

[lowmax_5]

Zitat:

Ich verstehe das Problem so: finde für jedes Element aus Menge2 eine Summe aus Elementen aus Menge1, sodass kein Element aus Menge1 doppelt verwendet wird (?)

Ja, das ist korrekt. In Menge B sollen der Einfachheit halber auch alle Elemente verwendet werden. Nach dem Studium Eurerer Beiträge scheint sich eine Lösung für mich wie folgt darzustellen:

1. Bilde Summen Menge1 und und Menge2 ==> Wenn gleich, mache weiter
2. Nun alle Permutationen aus Menge1 erzeugen und Summen bilden
3. Ist die Summe der Permutation in Menge2 enthalten => Wenn Ja=gültig, wenn Nein dann löschen
4. Nun alle Kombinationen bilden, die auf die Gesamtsumme kommen. ==> Diese Kombinationen markieren
5. Sortieren nach den einfachsten Kombinationen ( Am wenigsten summierende Elemente)
Fertig!

Kann das funktionieren? Was meint Ihr dazu?

[JasonDX]

Zitat von lowmax_5:

1. Bilde Summen Menge1 und und Menge2 ==> Wenn gleich, mache weiter
2. Nun alle Permutationen aus Menge1 erzeugen und Summen bilden
3. Ist die Summe der Permutation in Menge2 enthalten => Wenn Ja=gültig, wenn Nein dann löschen
4. Nun alle Kombinationen bilden, die auf die Gesamtsumme kommen. ==> Diese Kombinationen markieren
5. Sortieren nach den einfachsten Kombinationen ( Am wenigsten summierende Elemente)
Fertig!

Kann das funktionieren? Was meint Ihr dazu?

Du wirst bei 2. scheintern. Nicht bei der Implementierung, sondern bei der Laufzeit.

Bau die Lösung schrittweise auf, und wirf nicht funktionierende Lösungen so schnell wie möglich weg.

[Neutral General]

Mh habe mal schnell was zusammengetippt (Ist in keinster Weise perfekt, aber funktioniert schnell und ohne Probleme).
Es geht in erster Linie ums Prinzip.

Ist jetzt allerdings in C#:

Code:

class Program
{
   private static int GetMaxFittingValueIndex(List<int> list, int DestValue)
   {
      int currIdx = 0;
      for (int i=list.Count-1; i >= 0; i--)
      {
         if (DestValue - list[i] == 0)
            return i;
         else
         if ((DestValue - list[i] > 0) && (list[i] > list[currIdx]))
            currIdx = i;
      }

      return currIdx;
   }

   static void Main(string[] args)
   {
      List<int> MengeA = new List<int>(new int[] { 2, 6, 7, 1, 6, 15, 7, 4, 1 });
      List<int> MengeB = new List<int>(new int[] { 16, 13, 9, 11 });
      Dictionary<int, List<int>> SummenMengeC = new Dictionary<int, List<int>>();

      Console.Write("MengeA: ");
      for (int i = 0; i < MengeA.Count; i++)
         Console.Write(MengeA[i].ToString()+",");
      Console.WriteLine();

      Console.Write("MengeB: ");
      for (int i = 0; i < MengeB.Count; i++)
         Console.Write(MengeB[i].ToString()+",");
      Console.WriteLine();

      MengeA.Sort();
      for (int i=0; i < MengeB.Count; i++)
      {
         List<int> currSummeList = new List<int>();
         int currSumme = 0;
         while (currSumme < MengeB[i])
         {
            int idx = GetMaxFittingValueIndex(MengeA, MengeB[i] - currSumme);
            currSumme += MengeA[idx];
            currSummeList.Add(MengeA[idx]);
            MengeA.RemoveAt(idx);
         }

         SummenMengeC.Add(MengeB[i], currSummeList);
      }

      Console.WriteLine();
      Console.WriteLine("Ergebnis:");

      foreach(int zahl in SummenMengeC.Keys)
      {
         Console.Write(zahl.ToString() + " = ");
         for (int i=0; i < SummenMengeC[zahl].Count; i++)
         {
            if (i < SummenMengeC[zahl].Count - 1)
               Console.Write(SummenMengeC[zahl][i].ToString() + "+");
            else
               Console.Write(SummenMengeC[zahl][i].ToString());
         }
         Console.WriteLine();
      }

      Console.ReadLine();
   }
}

Habe ich was nicht beachtet? Bin mir nicht sicher ob das immer die beste Lösung erzeugt, könnte es mir aber vorstellen.
Irgendwelche Gedanken dazu?

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

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