Жадный алгоритм Метод Java/firstFit

Question

Я беру структуры данных и алгоритмы с классом Java в своем местном колледже, и я полностью придерживаюсь своего текущего задания на домашнюю работу. Проблема заключается в следующем:

Напишите программу, которая упаковывает объекты различных грузов в контейнеры. Каждый контейнер может содержать максимум 10 фунтов.

Программа использует жадный алгоритм, который помещает объект в первый бит, в который он поместится.

Я не прошу, чтобы моя домашняя работа была выполнена для меня, я просто очень надеюсь, что она будет направлена ​​в правильном направлении. У меня есть программа, очень близкая к работе, но я просто не могу заставить ее функционировать на 100% правильно. Я могу получить первый контейнер для хранения нужного количества веса, но после этого остальные мои контейнеры содержат только одно значение веса для каждого контейнера. Вот то, что я до сих пор ....

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(); 
    } 
} 

А вот вывод, что я получаю ...

Введите число объектов: 6

Введите вес объекты: 7 5 2 3 5 8

Контейнер 1 содержит объекты с весом [7,0, 2,0]

Контейнер 2 содержит объекты с весом [5,0]

Контейнер 3 содержит объекты с весом [3,0]

контейнер 4 содержит объекты с весом [5,0]

Контейнер 5 содержит объекты с весом [8,0]

---

И это то, что выход должен быть ...

введите число объектов: 6

введите вес объектов: 7 5 2 3 5 8

Контейнер 1 содержит объекты с весом [7,0, 2,0]

Контейнер 2 содержит объекты с весом [5,0, 3,0]

Контейнер 3 содержит объекты с вес [5,0]

контейнер 4 содержит объекты с весом [8,0]

Answer 1

Там проблема в вашем firstFit метода.

Что вы делаете, вы только пытаетесь добавить элемент в первый бит в BinList. Чтобы добиться того, чего вы ожидаете, вам нужно попытаться добавить элемент ко всем ячейкам в списке. Затем вы должны проверить, можете ли вы добавить или нет. Если нет, вы должны использовать новый ящик и добавить его в следующий список.

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;