knapsack_single.c (1409B)
1 #include <ctype.h> 2 #include <limits.h> 3 #include <stdio.h> 4 #include <time.h> 5 6 #include "knapsack.h" 7 #include "util.h" 8 9 #ifdef bell 10 #define knapsack knapsack_bell 11 #elif defined(greed) 12 #define knapsack knapsack_greed 13 #elif defined(full) 14 #define knapsack knapsack_full 15 #else 16 #error You need to define either bell, greed, or full 17 #endif 18 19 static long long int 20 input(long long minval, long long maxval) 21 { 22 unsigned char len = 0, arr[UCHAR_MAX]; 23 24 for (int c = getchar(); !isspace(c) && c != EOF; c = getchar()) 25 arr[len++] = c; 26 arr[len] = '\0'; 27 return estrtonum(arr, minval, maxval); 28 29 } 30 31 int 32 main(int argc, char *argv[]) 33 { 34 argv0 = argv[0]; 35 unsigned int k = input(0, UINT_MAX); 36 unsigned int w = input(0, UINT_MAX), 37 *m = emalloc(sizeof(*m) * k), 38 *c = emalloc(sizeof(*c) * k); 39 40 unsigned int len; 41 for (len = 0; len < k; ++len) 42 m[len] = input(0, UINT_MAX); 43 for (len = 0; len < k; ++len) 44 c[len] = input(0, UINT_MAX); 45 46 BitChunk *out = ecalloc(k/64 + 1, sizeof(*out)); 47 clock_t solve_time = clock(); 48 if (knapsack(k, w, m, c, out) < 0) 49 eprintf("knapsack:"); 50 solve_time = clock() - solve_time; 51 printf("%f\n", (double)solve_time / CLOCKS_PER_SEC); 52 long saved_number = -1; 53 for (len = 0; len < k; ++len) { 54 if (CHECK(out, len)) { 55 if (saved_number >= 0) 56 printf("%ld ", saved_number); 57 saved_number = len; 58 } 59 } 60 if (saved_number >= 0) 61 printf("%ld\n", saved_number); 62 }