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

25.23 (Optimal bin packing) Rewrite the preceding program so that it finds an optimal solution that packs all objects using the smallest number of containers.

What is the time complexity of your program?

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.Arrays;

public class Exercise23 {
private List<Integer> solution = new ArrayList<Integer> ();
 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 = 0;
  while(!objects.isEmpty()) {
   Exercise23 exercise23=new Exercise23();
   exercise23.hasGoalSum(objects,10);
   System.out.println("Container " + ++container + " contains objects with weight " + exercise23.solution);
   objects.removeAll(exercise23.solution);
  }
  System.out.println("The optimal number of bins is "+(container));
  
 }

private boolean hasGoalSum(List<Integer> list, int goal)
{
    // this if statement is the key to making this algorithm fast
    // since the algorithm is recursive it ends up eliminating many combinations
    // that don't need to be tested
    if (list.isEmpty () || goal > sumList(list) || goal < Collections.min (list))
    {
        return false;
    }

    // next we remove items from the list that are greater than the goal
    // since the can't be used to sum up to the goal
    list = rejectIfGreaterThanGoal (list, goal);
    if (list.contains (goal))
    {
        solution.add (goal);
        return true;
    }

    // if we don't have a solution yet we take the biggest item from the list and
    // and check if combining it with any of the remaining items will result
    // in an answer. If not, we then recursively call with a smaller list a
    // new subgoal. If there's still no solution we move to the next biggest
    // item in the list and so on until exhausting the list or finding a solution.
    while (!list.isEmpty ())
    {
        int m = Collections.max (list);
        list.remove ((Integer) m);
        if (list.contains (goal - m))
        {
            solution.add (m);
            solution.add (goal - m);
            return true;
        }
        if (hasGoalSum (list, goal - m))
        {
            solution.add (m);
            return true;
        }
    }

    return false;
}

private int sumList (List<Integer> list)
{
    int sum = 0;
    for (Integer num : list)
    {
        sum += num;
    }
    return sum;
}

private List<Integer> rejectIfGreaterThanGoal (List<Integer> list, int goal)
{
    List<Integer> newList = new ArrayList<> ();
    for (Integer i : list)
    {
        if (i <= goal)
        newList.add (i);
    }
    return newList;
}

}