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?
Michael
"Programmers talk about software development on weekends, vacations, and over meals not because they lack imagination,
but because their imagination reveals worlds that others cannot see."