Rekursion Kisten befüllen

[El Hadji]

Servus Community,
Ich habe wieder mal eine Frage. Ich habe eine Problemstellung ich muss schauen ob eine Liste von Gegenständen(also die Gewichte jeweils) in maxAnzahl Kisten und die jeweils maxGewicht gepackt werden können.
Ich bin wiefolgt vorgegangen:

 Arrays.sort(lasten);
        for (int left = 0, right = lasten.length-1; left < right; left++, right--)
        {
            int temp = lasten[left];
            lasten[left] = lasten[right];
            lasten[right] = temp;
           
        }

Jetzt habe ich natürlich das Problem das meine Rekursion falsch zuteilt.
Bei folgendem Beispiel:
[19, 8, 9, 10, 3, 20, 12],4,21)
Mein Algorythmus geht so vor:
{20} = 20
{19} = 19
{12,8} = 20
{10,9,3} = 22 also falsch

aber er müsste so zuteilen
{20}
{19}
{12,9}
{10,8,3}

ich bitte um Hilfe!
mfg El Hadji

 

[mihe7]

Ich habe wieder mal eine Frage.

Dich wird man aber wirklich nicht mehr los, oder? 😉

Jetzt habe ich natürlich das Problem das meine Rekursion falsch zuteilt.

Welche Rekursion?

Dann: wofür steht die Variable lasten? Wie sind die Zahlen in Deinem Beispiel zu verstehen? Und was soll uns Deine Schleife sagen?

 

[El Hadji]

Sorry ich hab den falschen Code reinkopiert -.-
Hier der richtige:

package bins;


import java.util.*;

public class Packen
{
 
    public Packen()
    {
     
    }

   
    public boolean istPackbar(int [] gewichte, int maxAnzahl, int maxGewicht)
    {
       
        Arrays.sort(gewichte);
       
        for (int left = 0, right = gewichte.length-1; left < right; left++, right--)
        {
            int temp = gewichte[left];
            gewichte[left] = gewichte[right];
            gewichte[right] = temp;
           
        }
       
       
        int [] kistengewicht = new int [maxAnzahl];
        packen(gewichte, kistengewicht,0);
        Arrays.sort(kistengewicht);
        //return kistengewicht;
       
        if(kistengewicht[kistengewicht.length-1] > maxGewicht)
        {
            return false;
        }
       
        else
        return true;
       
       
       
    }
   
    public void packen(int [] gewichte, int [] kistengewicht, int zaehler)
    {
      
       Arrays.sort(kistengewicht);
       kistengewicht[0] += gewichte[zaehler];
       zaehler++;
    
      
       if(zaehler != gewichte.length)
       {
           packen(gewichte, kistengewicht, zaehler);
        }
     
      
    }
}

Mit viel Glück bist mich ab Donnerstag los, wenn du mir jetzt noch schnell Rekursion reinprügelst ;-)

 

[Hutzli]

[19, 8, 9, 10, 3, 20, 12],4,21)

Ich nehme an, [19, 8, 9, 10, 3, 20, 12] steht für die Gewichte, welche auf 4 Pakete mit Maximalgewicht 21 aufgeteilt werden sollen. Ist das korrekt?

 

[El Hadji]

Genau

 

[Hutzli]

Was passiert denn in dem folgenden Fall:
Zu verteilende Gewichte: 19, 8, 9, 10, 3, 20, 12
Anzahl Pakete: 4
Maximal Gewicht der Pakete: 19

Also, wenn nicht jedes zu verteilende Gewicht einem Paket zugeordnet werden kann aufgrund der oberen Schranke (Maximalgewicht Paket) oder auch, wenn es zu wenig Pakete gibt, um alle Gewichte zu verteilen.

 

[Hutzli]

Was passiert denn in dem folgenden Fall:
Zu verteilende Gewichte: 19, 8, 9, 10, 3, 20, 12
Anzahl Pakete: 4
Maximal Gewicht der Pakete: 19

Also, wenn nicht jedes zu verteilende Gewicht einem Paket zugeordnet werden kann aufgrund der oberen Schranke (Maximalgewicht Paket) oder auch, wenn es zu wenig Pakete gibt, um alle Gewichte zu verteilen.

Ich sehe gerade, dass "istPacken" prüft, ob das ganze zuteilbar ist. Von dem her hat sich die Frage erledigt, Sorry.

 

[Hutzli]

Als Lösung würde ich mal folgenden Vorschlag aus dem Ärmel schütteln:
Algo-Ablauf:

1. Finde den grössten Eintrag:
   1. Iteriere über Array, beginne beim nächst höchsten Eintrag und versuche, das Paket zu vervollständigen
   2. Entferne die verwendeten Einträge aus den noch vorhandenen zu bearbeitenden Einträgen.
2. Beginne bei 1, wenn unbearbeitete Einträge vorhanden.

Das ergäbe in deinem Fall:

1. Grösster Eintrag: 20
   1. Einträge zur Vervollständigung: keine -> Paketgewicht: 20
   2. Entferne 20
2. Grösster Eintrag: 19
   1. Einträge zur Vervollständigung: keine -> Paketgewicht: 19
   2. Entferne 19
3. Grösster Eintrag: 12
   1. Einträge zur Vervollständigung: 9 -> Paketgewicht: 21
   2. Entferne 12,9
4. Grösster Eintrag: 10
   1. Einträge zur Vervollständigung: 8,3 -> Paketgewicht: 21
   2. Entferne 10,8,3
5. Keine Einträge mehr = Fertig

 

[mihe7]

Genau

Ach so... Dann: https://de.wikipedia.org/wiki/Behälterproblem

 

[El Hadji]

Ok danke für eure Tipps. Ich bin auch auf eine Lösung gekommen:

package bins;

import java.util.*;

public class Packen
{
   
    public Packen()
    {
      
    }

 
    public boolean istPackbar(int [] gewichte, int maxAnzahl, int maxGewicht)
    {
        ArrayList<Integer> gewicht = new ArrayList<>();
        ArrayList<Integer> kisten = new ArrayList<>();
        for(int i=0;i<maxAnzahl;i++)
        {
            kisten.add(0);
        }
        for(Integer d : gewichte)
        {
            gewicht.add(d);
        }
       
       ArrayList<Integer> max = gibMax(gewicht,maxGewicht,kisten);
       if(max.size() == gewicht.size())
       {
           return true;
        }
       
        else return false;
    }
   
     private ArrayList<Integer> gibMax(ArrayList<Integer> gewicht, int maximalGewicht, ArrayList<Integer> kisten)
    {
        ArrayList<Integer> best = new ArrayList<>();;
        if(gewicht.isEmpty())
        {
            return best;
        }
        ArrayList<Integer> copy = new ArrayList<Integer>(gewicht);
        int d = copy.remove(0);
        for(int i=0;i<kisten.size();i++)
        {
            ArrayList<Integer> erg = new ArrayList<>();
            if(kisten.get(i)+d <= maximalGewicht)
            {
                kisten.set(i,kisten.get(i)+d);
                erg = gibMax(copy,maximalGewicht,kisten);
                erg.add(d);
                kisten.set(i,kisten.get(i)-d);
            }
            if(best.size() < erg.size())
            {
                best = new ArrayList<>(erg);
            }
        }
        ArrayList<Integer> ergOhne = gibMax(copy,maximalGewicht,kisten);
        if(ergOhne.size() > best.size())
            return ergOhne;
        return best;
    }  
}

 

[El Hadji]

Gibts auch eine Möglichkeit mir ausgeben zu lassen, welche Gewichte ich in welche Kiste gelegt habe?
Dann nerv ich wirklich nicht mehr^^