teilsummenproblem, effizienter algo?

TheTester

tach folks

hab ne frage zu einem problem besser gesagt zum teilsummenproblem (glaub
das heisst auch scanline problem).
ist es möglich dieses problem in vernünftiger zeit zu lösen? bzw. gibt es
einen effizienten algorithmus dafür oder gehört das problem mit zu der klasse wie zb. das rucksackproblem, oder das problem des handlungsreisenden (keine approximation)

bye

tt

ist NP-hart

TheTester

gut dann brauch ich mir keine gedanken über die effizienz machen weils eh alles sch**** ist

thx

bye

tt

mady

Wenn ich Dich richtig verstanden habe, suchst Du einen Algo um die grösste Teilsumme von zusammenhängenden Elementen in einem Vektor zu finden. Hier mal eine Version:

int max_sum(int v[], int n)
{
    int i, max = 0, ende = 0;

    for (i = 0; i < n; i++) {
        ende += v[i];
        if (ende < 0)
            ende = 0;
        if (max < ende)
            max = ende;
    }

    return max;
}

Laufzeit O(n).

TheTester

mady
****

für wieviele elemente hast dus getestet?

bye

tt

TheTester

ach ja und ich suche nicht die größte teilsumme ;), sorry wenn das falsch rübergekommen ist das was ich brauche ist du gibst eine zahl ein, und lässt dir aus einer gegebenen menge von zahlen die möglichkeiten ausgeben mit der sich diese zahl errechnen lässt den algo dazu hab ich auch nur war ja meine frage ob sich das bei großen eingaben in einer vernünftigen zeit lösen lässt

bye

tt

mady

ups.... naja.... Für das Problem habe ich gerade auch nichts parat. Sorry.