Greedy Algorithm Java/metodo firstFit

Question

Sto prendendo una struttura di dati e algoritmi con classe Java presso il mio college locale, e sono completamente bloccato sul mio attuale compito a casa. Il problema è il seguente ...

Scrivere un programma che raggruppa gli oggetti di vari pesi in contenitori. Ogni contenitore può contenere un massimo di 10 sterline.

Il programma utilizza un algoritmo avido che posiziona un oggetto nel primo raccoglitore in cui si inserirà.

Non sto chiedendo di fare i compiti per me, spero solo di essere indicato nella giusta direzione. Ho il programma davvero vicino al lavoro, ma non riesco a farlo funzionare correttamente al 100%. Sono in grado di ottenere il primo contenitore per contenere la giusta quantità di peso, ma in seguito il resto dei miei contenitori contiene solo un valore di peso per contenitore. Ecco quello che ho finora ....

import java.util.ArrayList; 


public class Lab20 { 
    public static void main(String[] args) { 
     final java.util.Scanner input = new java.util.Scanner(System.in); 

    System.out.print("Enter the number of objects: "); 
    double[] items = new double[input.nextInt()]; 
    System.out.print("Enter the weight of the objects: "); 
    for (int i = 0; i < items.length; i++) { 
     items[i] = input.nextDouble(); 
    } 

    ArrayList<Bin> containers = firstFit(items); 

    //Display results 
    for (int i = 0; i < containers.size(); i++) { 
     System.out.println("Container " + (i + 1) 
       + " contains objects with weight " + containers.get(i)); 
    } 
    input.close(); 
} 

//Greedy Algorithm?? 
public static ArrayList<Bin> firstFit(double[] items) { 
    ArrayList<Bin> list = new ArrayList<>(); 
    Bin bin = new Bin(); 

    list.add(bin); 

    for (int i = 0; i < items.length; i++) { 
     if (!bin.addItem(items[i])) { 
      Bin bin2 = new Bin(); 
      list.add(bin2); 
      bin2.addItem(items[i]); 
      } 
     } 
     return list; 
    } 
} 

//Bin Class 
class Bin { 
    private ArrayList<Double> objects = new ArrayList<>(); 
    private double maxWeight = 10; 
    private double totalWeight = 0; 

    public Bin() { 
    } 

    public Bin(double maxWeight) { 
     this.maxWeight = maxWeight; 
    } 

    //Or is this supposed to be the Greedy algorithm?? 
    public boolean addItem(double weight) { 
     if ((totalWeight+weight) <= maxWeight) { 
      objects.add(weight); 
      totalWeight += weight; 
      return true; 
     } 
     else { 
      return false; 
     } 
    } 

    public int getNumberOfObjects() { 
     return objects.size(); 
    } 

    @Override 
    public String toString() { 
     return objects.toString(); 
    } 
} 

Ed ecco l'output che io sono sempre ...

Inserire il numero di oggetti: 6

Immettere il peso del oggetti: 7 5 2 3 5 8

contenitore 1 contiene oggetti con peso [7.0, 2.0]

contenitore 2 contiene oggetti con peso [5,0]

01.235.164,106174 millions

contenitore 3 contiene oggetti con peso [3.0]

Contenitore 4 contiene oggetti con peso [5,0]

Container 5 contiene oggetti con peso [8,0]

---

E questo è ciò che il uscita dovrebbe essere ...

Inserire il numero di oggetti: 6

Inserire il peso degli oggetti: 7 5 2 3 5 8

Container 1 contiene oggetti con peso [7.0, 2.0]

contenitore 2 contiene oggetti con peso [5.0, 3.0]

contenitore 3 contiene oggetti con peso [5,0]

Contenitore 4 contiene oggetti con peso [8,0]

Answer 1

C'è un problema nel vostro FirstFit metodo.

Quello che fai è, si tenta solo di aggiungere un elemento al primo cestino in BinList. Per ottenere ciò che ti aspetti, devi provare ad aggiungere l'articolo a tutti i raccoglitori nell'elenco. Quindi dovresti controllare se puoi aggiungere o meno. In caso contrario, è necessario utilizzare un nuovo raccoglitore e aggiungere all'elenco come segue.

for (int i = 0; i < items.length; i++) { 
    boolean added=false;  
    for(Bin bin: list){ 
     if(bin.addItem(items[i])){ 
      added=true;   
      break; 
     } 
    } 
    if(!added){ 
     Bin bin=new Bin(); 
     bin.addItem(items[i]); 
     list.add(bin); 
    } 
} 
return list;