Geek Answers Handbook

Greedy Algorithm Java / firstFit Method

I take data structures and algorithms with the Java class at my local college, and I fully adhere to my current homework assignment. The problem is this ...

Write a program that packs objects of various weights into containers. Each container can contain a maximum of 10 pounds.

The program uses a greedy algorithm that puts the object in the first bit in which it fits.

I do not ask that my homework be done for me, I just really hope that it will be sent in the right direction. I have a program that is very close to work, but I just can’t get it to function 100% correctly. I can get the first container to store the right amount of weight, but after that the rest of my containers contain only one weight value for each container. Here is what I still have ...

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 result that I get ...

Enter the number of objects: 6

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

Container 1 contains objects with a weight of [7.0, 2.0]

Container 2 contains objects with a weight of [5.0]

Container 3 contains objects with a weight of [3.0]

Container 4 contains objects with a weight of [5.0]

Container 5 contains objects with a weight of [8.0]

And this is what should happen ...

Enter the number of objects: 6

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

Container 1 contains objects with a weight of [7.0, 2.0]

Container 2 contains objects with a weight of [5.0, 3.0]

Container 3 contains objects with a weight of [5.0]

Container 4 contains objects with a weight of [8.0]

+5
source share
1 answer

There is a problem in your firstFit method.

What you do, you are only trying to add an element to the first bit in a BinList. To achieve what you expect, you need to try adding an item to all the cells in the list. Then you should check if you can add or not. If not, you need to use a new box and add it to the following list.

 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;
+3
source

More articles:


All Articles