Multiple knapsack problem solution using backtracking (with a smarter candidate generation function, and written in C)

backtracking_mkp.c

/* Generate a sparse decision matrix using backtracking to solve the
   multiple knapsack problem. In the code I use the term "bin" instead
   of knapsack because I think "knapsack" is a dumb word. And sacks are
   too flexible, bins are sturdier.

   by @tlehman

   Problem: There are N items and M bins. For each of the items, there is
            a size, and for each bin, there is a capacity. We see an
            assignment of each of the N items to at least one bin so that
            the sum of items in each bin is no more than that bin's capacity.

   Solution: We use backtracking to find N assignments (item index, bin index)
*/
#include <stdio.h>
#include <stdbool.h>
#define N 43
#define M 7
#define MAXCANDIDATES N*M

const int items[N] = {6, 4, 2, 2, 2, 2, 2, 2, 5, 2, 2, 2, 2, 4, 2, 2, 2, 2, 6, 2, 2, 2, 2, 2, 4, 2, 4, 6, 5, 2, 2, 2, 2, 5, 3, 4, 4, 3, 4, 2, 6, 2, 4};
const int bins[M] = {10, 11, 22, 22, 22, 22, 20};

/* an assignment is a struct, we call the type asg */
typedef struct {
  int item;  /* index of item */
  int bin;   /* index of bin */
} asg;

bool finished = false;

bool satisfies_constraints(asg a[], int k) {
  int j_sums[M];
  int i,j,ai;

  for(j = 0; j < M; j++) {
    j_sums[j] = 0;
  }

  // sum up all the items in the j-th bin
  for(ai = 0; ai <= k; ai++) {
    i = a[ai].item;
    j = a[ai].bin;
    j_sums[j] += items[i];
    if(j_sums[j] > bins[j]) {
      return false;
    }
  }
  return true;
}

bool is_a_solution(asg a[], int k) {
  return satisfies_constraints(a, k) && (k == N-1);
}

void print_matrix(asg a[], int k) {
  int i, j;
  int ai = 0;
  int v;
  // sort a by j bin, i item

  for(j = 0; j < M; j++) {
    for(i = 0; i < N; i++) {
      if (i == a[ai].item && j == a[ai].bin) {
        printf("1 ");
        ai++;
      } else {
        printf("0 ");
      }
    }
    printf("\n");
  }
}

void process_solution(asg a[], int k) {
  print_matrix(a,k);
  finished = true;
}

/* At step k, a should have max(0, k-1) assignments already

   This function constructs the M(N-k) possible candidates
*/
void construct_candidates(asg a[], int k, asg c[], int *ncandidates) {
  int i, j, ai;
  bool i_taken = false;
  *ncandidates = 0;
  bool item_index_taken[N];

  /* make a map[int]bool to quickly check for used indices */
  for(ai = 0; ai < k; ai++) {
    item_index_taken[a[ai].item] = true;
  }

  /* for each of the i items, only append candidate if i is not in the item index*/
  for(i = 0; i < N; i++) {
    if (item_index_taken[i] == false) {
      for(j = 0; j < M; j++) {
        c[*ncandidates].bin = j;
        c[*ncandidates].item = i;
        (*ncandidates)++;
      }
      item_index_taken[i] = true;
    }
  }

}

void backtrack(asg a[], int k) {
  asg c[MAXCANDIDATES];    /* candidates for next position */
  int ncandidates;         /* next position candidate count */
  int i;

  if (is_a_solution(a,k)) {
    process_solution(a,k);
  } else {
    k = k+1;
    construct_candidates(a,k,c,&ncandidates);

    for(i=0; i < ncandidates; i++) {
      a[k] = c[i];
      if(satisfies_constraints(a, k)) {
        backtrack(a,k);
      }
      if (finished) return; /* terminate early */
    }
  }
}

void init_a(asg a[]) {
  int ai;
  for(ai = 0; ai < N; ai++) {
    a[ai].item = 0;
    a[ai].bin = 0;
  }
}

int main() {
  asg a[N];                  /* assignments of items to bins */
  init_a(a);

  backtrack(a, -1);

  return 0;
}