| 08.02.2008, 23:38 |
Auf diesen Beitrag antworten » |
| JROppenheimer |
nicht Rucksack sondern Subset Sum
Es geht um folgendes.
Gegeben sind eine Menge natürlicher Zahlen und ein Betrag.
Gefragt ist nach einem Algorithmus, der ausgibt, ob in der Menge Elemente sind, deren Summe den Betrag ergeben.
(ich hoffe ihr entschuldigt meine tipfaulheit)
Ich hab das jetzt versucht per dynamischer Programmierung zu implementieren, aber mal abgesehn vom IndexOutOfBounds, funktioniert es einfach nicht so, wie ich das gerne hätte. ... irgendwo hab ich einen Denkfehler ...
der code sieht so aus:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
|
public static bool test(int betrag, int[] zahlen)
{
bool[] teilsumme = new bool[betrag];
int[] benutzteElemente = new int[zahlen.GetLength(0)];
teilsumme[0] = true;
for (int i = 0; i < zahlen.GetLength(0); i++)
{
benutzteElemente[i] = 0;
}
for (int i = 0; i < betrag-1; i++)
{
teilsumme[i] = false;
}
for (int i = 1; i <= betrag; i++)
{
for (int j = 0; j <= zahlen.GetLength(0)-1; j++)
{
System.Console.WriteLine("i=" + i + " j=" + j);
System.Console.ReadKey();
if (i+1 - zahlen[j] > 0)
{
if ((teilsumme[i - zahlen[j]] = true) & (benutzteElemente[j] == 0))
{
teilsumme[i] = true;
benutzteElemente[j] = 1;
}
}
}
}
return teilsumme[betrag];
}
|
|
Ich bin nicht sicher wo mein Fehler ist. |
| 10.02.2008, 11:25 |
Auf diesen Beitrag antworten » |
| JROppenheimer |
Okay, da war ein kleines logisches problem. Die beiden Schleifen müssen genau anders herum geschachtelt werden, denn die elementare Erkentnis ist:
Ist eines der Elemente in der Summe zu B enthalten, dann ist es egal, WANN es dazu addiert wird, da Summen kommutativ sind!
Folglich betrachtet man jedes Element einmal und schaut, welche Summen (0...B)mit dem aktuell betrachteten Element erreichbar sind, diese ergeben sich aus den vorher betrachteten Elementen, und trägt für eben diese TRUE in die Tabelle ein und macht dann mit dem nächste Element weiter!
Der Code dazu sieht so aus:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
|
public static bool test(int betrag, int[] zahlen)
{
int B = betrag;
int n = zahlen.GetLength(0);
//Nun das Array erstellen mit den Werten von 0..B, also mit B+1 Elementen
bool[] teilsumme = new bool[B + 1];
for (int i = 0; i <= B; i++)
{
teilsumme[i] = false;
}
//Die 0 ist ja trivial darstellbar
teilsumme[0] = true;
for (int i = 0; i < n; i++)
{
for (int b = B; b >= 0; b--) //von oben nach unten
{
if (b - zahlen[i] >= 0) //wichtig ist hier auch die überprüfung mit = 0
{
if (teilsumme[b - zahlen[i]])
{
teilsumme[b] = true;
}
}
}
}
return teilsumme[betrag];
}
|
|
Mit den freundlichsten Grüßen! |
