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