Author: Stan Eisenstat
Subject: Why Binpack does twice as many backtracks
Date: Thursday, 13 Feb 2020, 14:41:38

I added some print statements to your bp() and ran a
very simple example:

  % ./Binpack 13 9 5 5 3 2 2 -opt
  Add item[0] = 9 to bin #0             1
  Add item[1] = 5 to bin #1             2
  Add item[2] = 5 to bin #1             3
  Add item[3] = 3 to bin #0             4
  Add item[4] = 2 to bin #1             5
  Add item[5] = 2 to bin #2             6
  Remove item[5] = 2 from bin #2        7
  Remove item[4] = 2 from bin #1        8
  Add item[4] = 2 to bin #2             9
  Remove item[4] = 2 from bin #2       10
  Remove item[3] = 3 from bin #0       11
  Add item[3] = 3 to bin #1            12
  Add item[4] = 2 to bin #0            13
  Add item[5] = 2 to bin #0            14

(the line numbers were added later for reference).

Note that bp() finds a complete assignment using 3 bins
after Line #6.  But in Line #9 it assigns Item #4 to
Bin #2 (a third bin), which Heuristic C should prevent.

This may explain why bp() does twice as many backtracks
as Hwk2/Binpack.

--Stan-