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).
-CFLAGS += -Wall -Wwrite-strings -Wstrict-prototypes -g -O2
+CFLAGS += -Wall -Wwrite-strings -Wstrict-prototypes -g -O2 --std=gnu99
LC_CTYPE=C
LDLIBS = -lpub -lglpk
LC_CTYPE=C
LDLIBS = -lpub -lglpk
static glp_prob *best_prob;
static AdjWord *best_adjmatrix;
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) {
static unsigned printcounter;
static AdjWord *xalloc_adjmatrix(void) {
adjall = ~((~(AdjWord)0) << m);
adjmatrix = xalloc_adjmatrix();
glp_term_out(GLP_OFF);
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) {
}
static AdjWord one_adj_bit(int bitnum) {
HAVE_PRINTED;
best = got;
HAVE_PRINTED;
best = got;
+ n_over_best = n / best;
if (best_prob) glp_delete_prob(best_prob);
best_prob = prob;
if (best_prob) glp_delete_prob(best_prob);
best_prob = prob;
goto again;
if (i == 0 && (adjmatrix[i] & (1+adjmatrix[i])))
goto again;
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]);
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;
again:
if (adjmatrix[i] == adjall)
return;