knapsack.c (3418B)
1 #include <errno.h> 2 #include <limits.h> 3 #include <stdlib.h> 4 5 #include "knapsack.h" 6 #include "util.h" 7 8 int 9 knapsack_bell(unsigned int k, unsigned int w, 10 unsigned int m[k], unsigned int c[k], 11 BitChunk out[k/64+1]) 12 { 13 unsigned int *dp = calloc((w + 1) * (k + 1), sizeof(*dp)); 14 if (!dp) { 15 errno = ENOMEM; 16 return -1; 17 } 18 19 for (unsigned int i = 1; i <= k; ++i) { 20 unsigned int weight = m[i-1]; 21 unsigned int cost = c[i-1]; 22 for (unsigned int wi = 0; wi <= w; ++wi) { 23 unsigned int prev = dp[(i-1)*(w+1) + wi]; 24 if (wi >= weight) { 25 unsigned int alt = 26 dp[(i-1)*(w+1) + (wi - weight)] + cost; 27 dp[i*(w+1) + wi] = MAX(alt, prev); 28 } else { 29 dp[i*(w+1) + wi] = prev; 30 } 31 } 32 } 33 34 unsigned int wi = w; 35 for (unsigned int i = k; i > 0; --i) { 36 unsigned int w_row = i*(w+1); 37 unsigned int prevrow = (i-1)*(w+1); 38 if (dp[w_row + wi] != dp[prevrow + wi]) { 39 SET(out, i-1); 40 wi -= m[i-1]; 41 } else { 42 UNSET(out, i-1); 43 } 44 if (wi == 0) 45 break; 46 } 47 48 free(dp); 49 return 0; 50 } 51 52 static void 53 sift_down(unsigned int n, float a[n], unsigned int idx[n], unsigned int root) 54 { 55 while (1) { 56 unsigned int left = 2 * root + 1; 57 unsigned int right = left + 1; 58 unsigned int largest = root; 59 60 if (left < n && a[left] > a[largest]) 61 largest = left; 62 if (right < n && a[right] > a[largest]) 63 largest = right; 64 65 if (largest == root) 66 break; 67 68 float tmp = a[root]; 69 a[root] = a[largest]; 70 a[largest] = tmp; 71 72 unsigned int tmpi = idx[root]; 73 idx[root] = idx[largest]; 74 idx[largest] = tmpi; 75 76 root = largest; 77 } 78 } 79 80 static void 81 heap_build(unsigned int n, float a[n], unsigned int idx[n]) 82 { 83 for (int i = n / 2 - 1; i >= 0; --i) 84 sift_down(n, a, idx, i); 85 } 86 87 static unsigned int 88 extract_max(unsigned int *n, float a[*n], unsigned int idx[*n]) 89 { 90 if (*n == 0) 91 return UINT_MAX; 92 93 unsigned int max_index = idx[0]; 94 95 --*n; 96 a[0] = a[*n]; 97 idx[0] = idx[*n]; 98 99 sift_down(*n, a, idx, 0); 100 101 return max_index; 102 } 103 104 int 105 knapsack_greed(unsigned int k, unsigned int w, 106 unsigned int m[k], unsigned int c[k], 107 BitChunk out[k/64+1]) 108 { 109 float *density = malloc(sizeof(*density) * k); 110 if (!density) { 111 errno = ENOMEM; 112 return -1; 113 } 114 for (unsigned int i = 0; i < k; ++i) { 115 density[i] = (float)c[i]/m[i]; 116 c[i] = i; /* reuse c array for indices */ 117 } 118 unsigned int heap_size = k; 119 heap_build(heap_size, density, c); 120 121 unsigned long weight = 0; /* weight can be larger than w - use long */ 122 while (heap_size > 0) { 123 unsigned int pos = extract_max(&heap_size, density, c); 124 if (pos == UINT_MAX) 125 break; 126 127 weight += m[pos]; 128 if (weight > w) { 129 weight -= m[pos]; 130 } else if (weight < w) { 131 SET(out, pos); 132 } else { 133 SET(out, pos); 134 break; 135 } 136 } 137 138 free(density); 139 return 0; 140 } 141 142 int 143 knapsack_full(unsigned int k, unsigned int w, 144 unsigned int m[k], unsigned int c[k], 145 BitChunk out[k/64+1]) 146 { 147 if (k > sizeof(long)*8) { 148 errno = ERANGE; 149 return -1; 150 } 151 unsigned long best_cost = 0; 152 for (unsigned long list = 0; list < (1UL << k); ++list) { 153 unsigned long weight = 0, cost = 0; 154 for (unsigned int i = 0; i < k; ++i) { 155 if (!(list & (1UL << i))) 156 continue; 157 weight += m[i]; 158 if (weight > w) 159 break; 160 cost += c[i]; 161 } 162 163 if (cost > best_cost) { 164 best_cost = cost; 165 out[0] = list; /* this function is not used above 64 166 - abuse this fact */ 167 } 168 } 169 return 0; 170 }