Pages

Monday, 13 February 2017

Chapter 25 Exercise 20, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

25.20 (Bin packing using first fit) Write a program that packs the objects of various weights into containers. Each container can hold a maximum of 10 pounds. The program uses a greedy algorithm that places an object into the first bin in which it would fit. Your program should prompt the user to enter the total number of objects and the weight of each object. The program displays the total number of containers needed to pack the objects and the contents of each container.

Does this program produce an optimal solution, that is, finding the minimum
number of containers to pack the objects?


import java.util.ArrayList;
import java.util.Scanner;

public class Exercise20 {

 public static void main(String[] args) {
  @SuppressWarnings("resource")
  Scanner input = new Scanner(System.in);
  System.out.print("Enter the number of objects: ");
  int numberOfObjects = input.nextInt();
  ArrayList<Integer> objects = new ArrayList<>();
  System.out.print("Enter the weights of the objects: ");
  for (int i = 0; i < numberOfObjects; i++) {
   objects.add(input.nextInt());
  }
  int container = 1;
  while(!objects.isEmpty()) {
   System.out.println("Container " + container++ + " contains objects with weight " + getConteiner(objects, 10));
  }
 }
 
 static String getConteiner(ArrayList<Integer> objects, int max) {
  String result = "";
  for (int i = 0; i < objects.size(); i++) {
   if(objects.get(i) <= max) {
    int tmp = objects.get(i);
    result += tmp + " ";
    objects.remove(i);
    return result + getConteiner(objects, max - tmp);
   }
  }
  return result;
 }

}

No comments :

Post a Comment