Rucksackproblem mit 2 unterschiedlichen maxGewicht

[El Hadji]

Servus Community,
Das Rucksackproblem versteh ich ja etwas. was mache ich aber wenn ich 2 unterschiedliche Begrenzungen habe.

Ich hätte das Beispiel ganz einfach mit dem Rucksackproblem gelöst und statt Gegenständen die BEstellungen genommen. Als maxGewicht wollte ich den Lagerplatz für die einzelnen Artikel nehmen, aber das sind ja 2 verschiedene Werte. Wie gehe ich da also vor?

public class Rucksackproblem
{

    public List<Gegenstand> getBesteAuswahl(List<Gegenstand> liste, double maxW) {
        double bestValue = getBestValue(liste,maxW,0);
        double restW = maxW;
        double restV = bestValue;
        ArrayList<Gegenstand> erg = new ArrayList<>();
        for(int k=0; k<liste.size(); k++) {
            //mit Gegenstaenden ab Index k kann restV erreicht werden, ohne restW zu überschreiten
            if(getBestValue(liste,restW,k+1) < restV) {
                Gegenstand g = liste.get(k);
                erg.add(g);
                restW -= g.weight;
                restV -= g.value;
            }
        }
        return erg;
    }
   
    /*
     * Liefert den Wert der optimalen Auswahl von Gegenstaenden mit Index >=k.
     */
    private double getBestValue(List<Gegenstand> liste, double maxW, int k) {
        double erg = 0;
        if(k == liste.size()) return erg;
        Gegenstand g = liste.get(k);
        if(g.weight <= maxW) {
            erg = g.value + getBestValue(liste,maxW-g.weight,k+1);
        }
        double ergOhne = getBestValue(liste,maxW,k+1);
        if(erg > ergOhne) {
            return erg;
        } else {
            return ergOhne;
        }
    }

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
}

mfg El Hadji

 

[mihe7]

Genauso, weil eine Bestellung mit zwei Artikeln entweder ganz oder gar nicht ausgeführt wird.

 

[El Hadji]

ja aber ich muss doch überprüfen ob das Lager mit Artikeln(0) und das Lager mit Artkeln(1) voll ist?

 

[mihe7]

Ja, und?

 

[El Hadji]

Ja, und?

Leider bin ich damit schon überfordert^^

 

[mihe7]

Du hast eine Liste von Bestellungen, dann kannst Du doch in Abhängigkeit der Artikelnummer die Gesamtmenge ermitteln. Die darf halt nicht überschreiten, was das Lager hergibt.