Example of a simple brute force solver

micrioKnap.c

#include <stdio.h>

typedef unsigned long long int llu;
llu BUDGET = 542;
const int ITEMS = 11;
llu PRICES[ITEMS] = {100, 100, 400, 23, 64, 39, 18, 39, 29, 39, 28};

#define CHECK_BIT(var, pos) ((var) & (1 << (pos)))

void printItems(llu mask) {
  int i;
  for (i = 0; i < ITEMS; i++) {
    if (CHECK_BIT(mask, i))
      printf("%llu ", PRICES[i]);
  }
}

llu total(llu mask) {
  llu i, sum = 0;
  for (i = 0; i < ITEMS; i++) {
    if (CHECK_BIT(mask, i))
      sum += PRICES[i];
  }
  return sum;
}

int main() {
  if (ITEMS > 63) {
    printf("Get a real SAT solver\n");
    return (1);
  }
  llu enough = 1 << ITEMS;
  llu mask, t, best = 0;
  for (mask = 0; mask < enough; mask++) {
    t = total(mask);
    if (t > best && t <= BUDGET) {
      best = t;
      printItems(mask);
      printf(" = %llu \n", t);
    }
  }
  return 0;
}