我正在本地社区大学学习 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] 的对象
最佳答案
您的firstFit 方法有问题。
您所做的是,您只尝试将一个元素添加到 BinList 中的第一个 bin。为了达到您的期望,您必须尝试将项目添加到列表中的所有容器中。然后你应该检查你是否可以添加。如果不是,则必须使用新的 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 - 贪心算法Java/firstFit方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37062803/