Rekursion Kisten befüllen

El Hadji

Bekanntes Mitglied
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:
Code:
 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
 

El Hadji

Bekanntes Mitglied
Sorry ich hab den falschen Code reinkopiert -.-
Hier der richtige:
Code:
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

Aktives Mitglied
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

Aktives Mitglied
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

Aktives Mitglied
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
 
Zuletzt bearbeitet:

El Hadji

Bekanntes Mitglied
Ok danke für eure Tipps. Ich bin auch auf eine Lösung gekommen:
Code:
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

Bekanntes Mitglied
Gibts auch eine Möglichkeit mir ausgeben zu lassen, welche Gewichte ich in welche Kiste gelegt habe?
Dann nerv ich wirklich nicht mehr^^
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
K Verstehe Rekursion nicht ganz Java Basics - Anfänger-Themen 7
P Frage zu Rekursion und Backtracking Java Basics - Anfänger-Themen 2
DiyarcanZeren Rekursion in Java Java Basics - Anfänger-Themen 5
M Variablen Rekursion mit 2 Parameteren Java Basics - Anfänger-Themen 4
sserio Rekursion größten Primfaktor finden funktioniert nicht Java Basics - Anfänger-Themen 8
M Lösungsweg Rekursion Java Basics - Anfänger-Themen 1
C StackOverflow bei Rekursion Java Basics - Anfänger-Themen 7
D Rekursion - Ich raffs nicht Java Basics - Anfänger-Themen 16
N Methoden Rekursion mit Kreisen Java Basics - Anfänger-Themen 7
P9cman Vokale in einem String überprüfen mittels Rekursion Java Basics - Anfänger-Themen 8
J Rekursion Java Basics - Anfänger-Themen 22
T Rekursion Programmierverständnis Java Basics - Anfänger-Themen 12
K Rekursion: Rechenmauer mit Array erstellen Java Basics - Anfänger-Themen 17
K Rekursion einer Zahlenfolge (Ab- und Aufzählung) Java Basics - Anfänger-Themen 6
Zeppi Rekursion Java Basics - Anfänger-Themen 15
V Backtracking und Rekursion Java Basics - Anfänger-Themen 15
L REKURSION Java Basics - Anfänger-Themen 13
Kirby.exe Rekursion Java Basics - Anfänger-Themen 7
N for Schleife durch Rekursion ersetzen Java Basics - Anfänger-Themen 6
X Rekursion Java Basics - Anfänger-Themen 3
H Rekursion Java Basics - Anfänger-Themen 2
D Erste Schritte Rekursion Java Basics - Anfänger-Themen 13
M Rekursion Tage Ansteckung gesamte Bevölkerung Java Basics - Anfänger-Themen 15
M Java Rekursion Java Basics - Anfänger-Themen 9
G Java Rekursion Java Basics - Anfänger-Themen 5
J Rekursion Klausur Aufgabe Java Basics - Anfänger-Themen 2
N Rekursion Java Basics - Anfänger-Themen 18
M Verständnisproblem der Rekursion bei Arrays Java Basics - Anfänger-Themen 8
X Rekursion Rätsel Java Basics - Anfänger-Themen 4
N Klassen Rekursion mit Feldern von Objekten Java Basics - Anfänger-Themen 14
W Rekursion Java Basics - Anfänger-Themen 0
D Konsolenausgabe Zahlenfolge Rekursion Java Basics - Anfänger-Themen 3
J Ping Pong Methode mit Rekursion Java Basics - Anfänger-Themen 1
N Rekursion Java Basics - Anfänger-Themen 1
B Rekursion Basic Java Basics - Anfänger-Themen 15
O Rekursion Mergesort Java Basics - Anfänger-Themen 18
G Rekursion Java Basics - Anfänger-Themen 20
M Rekursion Java Basics - Anfänger-Themen 7
F Hilfe bei Rekursion... Java Basics - Anfänger-Themen 4
A Mit Rekursion Zufallszahlen erstellen und größte finden Java Basics - Anfänger-Themen 5
B Rekursion Wurzel Java Basics - Anfänger-Themen 39
O Rekursion ordentlich aufschreiben Java Basics - Anfänger-Themen 2
B Rekursion verstehen Java Basics - Anfänger-Themen 4
O Rekursion Java Basics - Anfänger-Themen 2
E Rekursion verstehen. Java Basics - Anfänger-Themen 4
E Rekursion verstehen Java Basics - Anfänger-Themen 2
O Rekursion, String Java Basics - Anfänger-Themen 8
N Invertierte Rekursion??? Java Basics - Anfänger-Themen 5
M Bitte um Hilfe bei Quellcode (Rekursion) Java Basics - Anfänger-Themen 6
T Rekursion Warum bricht meine Funktion nicht ab Java Basics - Anfänger-Themen 4
A Hilfe bei Rekursion,Ich verstehe nicht,wie funktioniert die Rekursion in der Methode "walk" Java Basics - Anfänger-Themen 13
L Rekursion im Baum Java Basics - Anfänger-Themen 9
E Pfade eines Baums angeben ohne Rekursion Java Basics - Anfänger-Themen 20
L Rekursion Baumknoten Java Basics - Anfänger-Themen 8
L Rekursion größtes Zeichen Java Basics - Anfänger-Themen 8
L Rekursion Modulo Java Basics - Anfänger-Themen 7
I Rekursion Java Basics - Anfänger-Themen 11
H Rekursion Java Basics - Anfänger-Themen 7
N Methoden zur Rekursion (catalansche Zahlen) Java Basics - Anfänger-Themen 4
S Frage zu Rekursion... Java Basics - Anfänger-Themen 15
N Java catalansche Zahlen (Rekursion) Java Basics - Anfänger-Themen 5
S Noch eine Frage zur Rekursion... Java Basics - Anfänger-Themen 11
S Frage zu einer Rekursion Java Basics - Anfänger-Themen 15
F Methoden Abbruchbedingung bei Rekursion Java Basics - Anfänger-Themen 2
Z Rekursion Primzahlen Java Basics - Anfänger-Themen 1
K Rekursion Verständnisfrage Java Basics - Anfänger-Themen 19
L Methoden Rekursion gibt alten Wert wieder Java Basics - Anfänger-Themen 37
M Rekursion Minimums Suche Java Basics - Anfänger-Themen 12
J Rekursion Java Basics - Anfänger-Themen 5
F Aufgabe Rekursion Binärer Baum Java Basics - Anfänger-Themen 15
N Rekursion Java Basics - Anfänger-Themen 2
B Rekursion - Übung Java Basics - Anfänger-Themen 2
B Problem beim grundsätzlichen Verständnis bei Rekursion mit 2-dimensionalen Array Java Basics - Anfänger-Themen 6
P Rekursion Java Basics - Anfänger-Themen 19
G Rekursion Beispiel Java Basics - Anfänger-Themen 3
M Rekursion schreiben Java Basics - Anfänger-Themen 16
A Rekursion Funktion in eine Iterativ Funktion umwandeln Java Basics - Anfänger-Themen 9
T Array Rekursion Java Basics - Anfänger-Themen 1
B lineare und schlichte Rekursion Java Basics - Anfänger-Themen 1
A Rekursion Java Basics - Anfänger-Themen 2
B Rekursion Java Basics - Anfänger-Themen 3
A Rekursion stoppt an der falschen Stelle Java Basics - Anfänger-Themen 4
A Lineare Rekursion Java Basics - Anfänger-Themen 6
P Hilfe zur Rekursion? Java Basics - Anfänger-Themen 2
B Rekursion Schneeflocke - Kurze Frage zur Methode Java Basics - Anfänger-Themen 11
L Rekursion Java Basics - Anfänger-Themen 4
S Rekursion Rückgabe - Türme von Hanoi Java Basics - Anfänger-Themen 16
kilopack15 Rekursion und Schleifen Java Basics - Anfänger-Themen 27
E Rekursion Java Basics - Anfänger-Themen 10
G rekursion nicht verstanden Java Basics - Anfänger-Themen 5
K Rekursion-Verständnisfrage Java Basics - Anfänger-Themen 4
E Methoden String wird in Rekursion nicht überschrieben Java Basics - Anfänger-Themen 2
T 2fach Rekursion. Java Basics - Anfänger-Themen 4
N Rekursion mit if-Anweisung Java Basics - Anfänger-Themen 10
K Methoden Zahlensysteme umwandeln mittels Rekursion Java Basics - Anfänger-Themen 5
H Rekursion Binäre Suche Java Basics - Anfänger-Themen 2
P Methoden Primzahltest mit Rekursion Java Basics - Anfänger-Themen 3
C Rekursion überführen in eine normale methode Java Basics - Anfänger-Themen 1
M Methoden Rekursion nachvollziehen Java Basics - Anfänger-Themen 4
C Rekursion Java Basics - Anfänger-Themen 6

Ähnliche Java Themen

Neue Themen


Oben