Pages

Tuesday, 14 February 2017

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

25.21 (Bin packing with smallest object first) Rewrite the preceding program that uses a new greedy algorithm that places an object with the smallest weight 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.Collections;
import java.util.Scanner;

public class Exercise21 {

 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) {
  if(objects.isEmpty()) {
   return "";
  }
  String result = "";
  int min = Collections.min(objects);
  if(min <= max) {
   result += min + " ";
   objects.remove(new Integer(min));
   return result + getConteiner(objects, max - min);
  }
  return result;
 }

}

No comments :

Post a Comment