Check max Hamming weight in the other direction.

Once we've already got a solution, we can further winnow the set of
possible adjacency matrices, by ensuring the same bit is not set in
too many entries of adjmatrix (since if it were, some length-n stick
would have to be divided into enough pieces to make one at most the
already-known best result). This adds complexity to each step of the
recursion over possible matrices, but by early pruning it seems to cut
down the number of steps by rather more; I estimate a factor of four
speedup in pursuit of (n,m)=(10,7).

diff --git a/Makefile b/Makefile
index 5c571d284f051ed87f1a8a4c1b67c14ab3dc6e69..225239d8d0ff6d81578f9ee71665d95e38acc230 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,4 @@
-CFLAGS += -Wall -Wwrite-strings -Wstrict-prototypes -g -O2
+CFLAGS += -Wall -Wwrite-strings -Wstrict-prototypes -g -O2 --std=gnu99
 LC_CTYPE=C
 LDLIBS = -lpub -lglpk
 

diff --git a/main.c b/main.c
index 6f0df725949c9b26fccb613768f74c283bc9e591..3c1b123b2e71155b058bdc34d45f058f6db592f9 100644 (file)
--- a/main.c
+++ b/main.c
@@ -86,6 +86,9 @@ static double best;
 static glp_prob *best_prob;
 static AdjWord *best_adjmatrix;
 
+static int n_over_best;
+static int *weight;
+
 static unsigned printcounter;
 
 static AdjWord *xalloc_adjmatrix(void) {
@@ -96,6 +99,9 @@ static void prep(void) {
   adjall = ~((~(AdjWord)0) << m);
   adjmatrix = xalloc_adjmatrix();
   glp_term_out(GLP_OFF);
+  n_over_best = n / best;
+  weight = (int *)malloc(m*sizeof(int));
+  for (int j = 0; j < m; j++) weight[j] = 0;
 }
 
 static AdjWord one_adj_bit(int bitnum) {
@@ -300,6 +306,7 @@ static void optimise(int doprint) {
   HAVE_PRINTED;
 
   best = got;
+  n_over_best = n / best;
 
   if (best_prob) glp_delete_prob(best_prob);
   best_prob = prob;
@@ -331,9 +338,20 @@ static void iterate_recurse(int i, AdjWord min) {
       goto again;
     if (i == 0 && (adjmatrix[i] & (1+adjmatrix[i])))
       goto again;
+    for (int j = 0; j < m; j++)
+      if (adjmatrix[i] & (1 << j))
+        weight[j]++;
+    for (int j = 0; j < m; j++)
+      if (weight[j] >= n_over_best)
+        goto takeout;
 
     iterate_recurse(i+1, adjmatrix[i]);
 
+   takeout:
+    for (int j = 0; j < m; j++)
+      if (adjmatrix[i] & (1 << j))
+        weight[j]--;
+
   again:
     if (adjmatrix[i] == adjall)
       return;