Skip to content

Instantly share code, notes, and snippets.

@tlehman
Last active April 18, 2016 21:25
Show Gist options
  • Save tlehman/909d60393457a484294890370c059c20 to your computer and use it in GitHub Desktop.
Save tlehman/909d60393457a484294890370c059c20 to your computer and use it in GitHub Desktop.
Multiple knapsack problem solution using backtracking (with a smarter candidate generation function, and written in 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment