Rekursion ArrayList zurückgeben Rucksack

[alex2345]

Habe folgendes Programm geschrieben:
Liefert nach Eingabe des maximalen Gewichtes die maximale Lösung was man in einen Rucksack einpacken kann.

public class Test2
{
    
    int[] gewichte = {8, 15, 26, 30, 45};
    
    public Test2()
    {}

    int packe(int maxWeight)
    {
        return packe(0, maxWeight);
    }
    
    int packe(int k, int freiesGewicht)
    {
        if(k >= gewichte.length)
            return 0;
        int wert1;
        int wert2;
        wert1 = packe(k+1,freiesGewicht);
        int d = gewichte[k];
        if(d <= freiesGewicht)
        {
            wert2 = d + packe(k+1,freiesGewicht-gewichte[k]);
        } else {
            wert2 = -1;
        }
        return Math.max(wert1,wert2);
    }
}

Nun möchte ich dieses Programm mit ArrayLists schreiben, und als Rückgabewert eine ArrayList mit den Gewichten die eingepackt wurden. Ich weiß zwar dass man es erst zur Ergebnis-ArrayList hinzufügen muss und danach wieder löschen aber wie genau hab ich doch nicht mehr viel Ahnung. Noch dazu weiß ich nicht wie ich den Basisfall umschreiben muss. Was soll der zurückliefern? Eine Kopie der Originalliste weil man doch alles einpacken konnte? Muss die rekursive Methode eigentlich selber schon eine ArrayList als Rückgabewert haben?

Vielen Dank für Tipps

import java.util.*;

public class ArrayL
{
    
    public ArrayL()
    {}

    public ArrayList<Integer> packe()
    {
        ArrayList<Integer> gewichte = new ArrayList<Integer>();
        gewichte.add(80);
        gewichte.add(46);
        gewichte.add(47);
        gewichte.add(48);
  //      gewichte.add(99);
        ArrayList<Integer> liste = new ArrayList<Integer>();
        ArrayList<Integer> max = new ArrayList<Integer>();
        return packe(0, 100, gewichte, liste, max);
    }
    
    ArrayList<Integer> packe(int k, int freiesGewicht, ArrayList<Integer> gewichte, ArrayList<Integer> liste, ArrayList<Integer> max)
    {
        int summeOhne;
        int summeMit;
        if(k >= gewichte.size())
            return new ArrayList<Integer> (gewichte);
        summeOhne = berechneSumme(packe(k+1, freiesGewicht, gewichte, liste, max));
        if(summeOhne > berechneSumme(max))
            max = liste;
        if(gewichte.get(k) <= freiesGewicht)
        {
            liste.add(gewichte.get(k));
            summeMit = berechneSumme(packe(k+1, freiesGewicht-gewichte.get(k), gewichte, liste, max));
            if(summeMit > berechneSumme(max))
                max = liste;
        } else {
            liste.remove(liste.size()-1);
            summeMit = -1;
        }
        return max;
    }
    
    public int berechneSumme(ArrayList<Integer> a)
    {
        int summe = 0;
        for(int i = 0; i < a.size(); i++)
        {
            summe = summe + a.get(i);
        }
        return summe;
    }
}

 

[bERt0r]

Musst du das denn rekursiv lösen (steht das in der Angabe)? Arrays sind in der Regel sehr viel einfacher iterativ abzuarbeiten.

 

[alex2345]

Müssen nicht aber ich beschäftige mich gerade mit Rekursion weil ich diese lernen möchte und ich bin mir nicht sicher ob das rekursiv nicht kürzer und einfacher zu lösen geht als iterativ. Die Gewichte habe ich nur zum ausprobieren reingeschrieben. Die ArrayList mit den Gewichten kann beliebig groß sein. Wenn ich da eine bestimmte Größe hätte wärs iterativ sicher einfacher, es soll aber variabel sein.

 

[U2nt]

Kann man jetzt nicht schon beliebig viele Gewichte reinstecken, oder habe ich mich verlesen?
Ich versteh's zwar nochnicht ganz (noch nicht gründlich genug gelesen, ist ja auch spät), aber mir scheints iterativ einfacher zu fallen. In Verbindung mit Listen denk ich ziemlich schnell an die for-each Schleife...

 

[alex2345]

Ja, sind beliebig viele Gewichte möglich. Auch die Obergrenze (hab ich mal mit 100 angegeben) kann man sich aussuchen. Mit einer einfachen for-each Schleife ist es glaube ich nicht getan, da mir diese nicht alle verschiedenen Möglichkeiten liefert wie ich die Gewichte zusammensetzen kann.