P. Fernandez P. Fernandez - 6 months ago 33
Java Question

Greedy Algorithm Java / firstFit method

I am taking a data structures and algorithms with Java class at my local community college, and I am completely stuck on my current homework assignment. The problem is as follows...

Write a program that packs the objects of various weights into containers. Each container can hold a max of 10 pounds.

The program uses a greedy algorithm that places an object into the first bin in which it will fit.

I am not asking for my homework to be done for me, I am just really hoping to be pointed in the right direction. I have the program really close to working but I just can't get it to function 100% properly. I am able to get the first container to hold the right amount of weight, but then after that the rest of my containers only hold one weight value per container. Here is what I have so far....

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


And here is the output that I am getting...

Enter the number of objects: 6

Enter the weight of the objects: 7 5 2 3 5 8

Container 1 contains objects with weight [7.0, 2.0]

Container 2 contains objects with weight [5.0]

Container 3 contains objects with weight [3.0]

Container 4 contains objects with weight [5.0]

Container 5 contains objects with weight [8.0]




And this is what the output should be...

Enter the number of objects: 6

Enter the weight of the objects: 7 5 2 3 5 8

Container 1 contains objects with weight [7.0, 2.0]

Container 2 contains objects with weight [5.0, 3.0]

Container 3 contains objects with weight [5.0]

Container 4 contains objects with weight [8.0]

Answer

There's a problem in your firstFit method.

What you do is, you only try to add an element to the first bin in the BinList. In order to achieve what you expect, you have to try to add the item to all the bins in the list. Then you should check whether you could add or not. If not, you have to use a new bin and add to the list as follows.

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;
Comments