贪心算法Java/firstFit方法

Question

我正在我当地的社区大学学习 Java class 的数据结构和算法，我完全被困在当前的家庭作业上。问题如下...

编写一个程序，将各种重量的物体装入容器中。每个容器最多可容纳 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 中的第一个 bin。为了达到您的期望，您必须尝试将项目添加到列表中的所有容器中。然后你应该检查你是否可以添加。如果没有，您必须使用新的垃圾箱并添加到列表中，如下所示。

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;

贪心算法Java/firstFit方法

Greedy Algorithm Java / firstFit method

java

greedy