1 #ifndef KNAPSACK_H_ 2 #define KNAPSACK_H_ 3 4 #include <stdint.h> 5 6 #ifdef __cplusplus 7 extern "C" { 8 #endif 9 10 typedef int (*knapsack_object_callback_t)(void *, unsigned long v, int64_t x); 11 12 struct knapsack_object_s { 13 const int64_t * tab; 14 unsigned int stride; 15 unsigned int offset; 16 unsigned int nelems; 17 int64_t bound; 18 knapsack_object_callback_t cb; 19 void * cb_arg; 20 }; 21 22 typedef struct knapsack_object_s knapsack_object[1]; 23 typedef struct knapsack_object_s * knapsack_object_ptr; 24 typedef const struct knapsack_object_s * knapsack_object_srcptr; 25 26 /* This interface solves a modular knapsack with the standard O(2^(n/2)) 27 * time, O(2^(n/2)) memory algorithm (one may do better both in time and 28 * memory). 29 * 30 * Solutions must have all coefficients in [-1,+1], and the combination 31 * must fit within the interval [-bound,+bound] 32 * 33 * The stride value exists because we also allow the possibility for the 34 * knapsack to be multi-dimensional. 35 * 36 * there's a trivial factor of two to be gained by constraining one 37 * coordinate -- however I keep the stuff this way for a while, because 38 * wraparounds are sometimes tricky, and may lead to missing solutions. 39 */ 40 extern int knapsack_solve(knapsack_object_ptr ks); 41 42 /* these are almost empty placeholders. the caller must proved the tab 43 * pointer himself */ 44 void knapsack_object_init(knapsack_object_ptr); 45 void knapsack_object_clear(knapsack_object_ptr); 46 47 #ifdef __cplusplus 48 } 49 #endif 50 51 #endif /* KNAPSACK_H_ */ 52