P R E L I M I N A R Y   S P E C I F I C A T I O N

					   Due 2:00 am, Friday, 6 February 2009

CPSC 223b  Homework #2    The Bin Packing Problem

(40) Write a program

	Binpack Bin_Size [Item_Size]* [-opt | -ff | -bf | -ffd | -bfd]*

that prints out the number of bins required to store the items whose sizes are
specified.  Here

  Bin_Size is the capacity of each bin and must be a positive integer.

  [Item_Size]* is a sequence of zero or more item sizes (which must be
    positive integers).

  [-opt | -ff | -bf | -ffd | -bfd]* is a sequence of zero or more flags (each
    either -opt or -ff or -bf or -ffd or -bfd) that specify how to compute the
    assignment.

and the following flags are recognized:

  -opt  Use backtracking to find the minimum number of bins required.

  -ff   Use the first-fit heuristic:  process the items in the order specified
	on the command line and put each item in the leftmost bin in which it
	would fit.

  -bf   Use the best-fit heuristic:  process the items in the order specified
	on the command line and put each item in the bin that would have the
	least amount of room remaining (the leftmost such bin in the case of
	ties).

  -ffd  Apply the first-fit heuristic, but first sort the items in decreasing
	order of size.

  -bfd  Apply the best-fit heuristic, but first sort the items in decreasing
	order of size first.

Note that the notation above means that the item sizes must all PRECEDE the
first function tag.

The number of bins is printed using

  printf ("%d\n", numberOfBins);

When more than one flag is specified, the corresponding numbers of bins appear
on separate lines in the order specified on the command line.  Flags may be
specified more than once.

Examples:

  % Binpack 100  31 41 59 26 53 58 97 93 23 84 62 64 33

  % Binpack 100  31 41 59 26 53 58 97 93 23 84 62 64 33 -opt -opt
  8
  8

  % Binpack 96  14 14 14 14 14 14 33 33 33 33 33 33 49 49 49 49 49 49  -ff -ffd
  10
  6

  % Binpack 96  14 14 14 14 14 14 33 33 33 33 33 33 49 49 49 49 49 49  -bf -bfd
  10
  6

Use the submit command to turn in the source file(s) for Binpack, a Makefile,
and your log file (see Homework #1).

YOU MUST SUBMIT YOUR FILES (INCLUDING THE LOG FILE) AT THE END OF ANY SESSION
WHERE YOU SPEND AT LEAST ONE HOUR WRITING OR DEBUGGING CODE, AND AT LEAST ONCE
EVERY FIVE HOURS DURING LONGER SESSIONS.  (ALL SUBMISSIONS ARE RETAINED.)


Notes:

1. Your program should assume that every item can fit in a bin and that no
   more than 100 (which should be a symbolic constant) Item_Size's will be
   specified.  However, there is no limit on the number of flags.

2. Your program should fail gracefully if any of the assumptions made above
   are violated.  Hint: With the right code, the value returned by atoi()
   can always be used, even if the argument specifying the capacity or item
   size is not a positive integer.

3. The general form of backtracking for this problem is something like:

     int bp (...)
     {
	 if all items have been placed in bins
	     return the total number of bins used
	 for each bin that we can place the next item in
	     place the item in that bin
	     call bp() recursively to find the minimum number of bins used
		to store all of the items given that the items already stored
		cannot be moved
	     remove the item from the bin
	 return the minimum number of bins needed
     }

4. To reduce the amount of backtracking required to find the optimal solution:

   a. presort the sizes in decreasing order;

   b. compute a lower bound on the number of bins by adding the sizes together,
      dividing by the capacity, and rounding up to the nearest integer; and
      quit when an assignment requiring that number of bins is found;

   c. keep track of the smallest number of bins found previously (initially
      this is just the number of items) and do not consider any (partial)
      assignment that would require at least that many bins;

   d. when the current item has the same size as the last item stored in the
      partial assignment, never place it in a bin to the left of the bin in
      which that last item was stored (modify accordingly if you try the bins
      in other than left-to-right order)
				     
   e. never place an item in a bin that has the same amount of room remaining
      as one that was tried previously for this item.

   Heuristics (d) and (e) will be worth at most 3 points each.

5. You may implement the sorting algorithm of your choice (efficiency is not
   important for at most 100 items), but you must start from scratch.  In the
   unlikely event that you do not know ANY algorithms, you may read about them
   in a book.  However, the Gilligan's Island Rule then applies.

6. Point to Ponder: How large can the ratio of N(ff)/N(opt) be?  NN(bf)/N(opt)?
   N(ffd)/N(opt)?  N(bfd)/N(opt)?

								CS-223-01/22/09