commit 709cc6b9f2baff6339a563620e0eb92183aa6a3c
parent a237bf2f62d1806163676315c60c8867bbcd1f4d
Author: Plat <plat@stellar-nexus.ru>
Date: Tue, 25 Nov 2025 20:34:42 +0000
Optimized knapsack.c
Diffstat:
4 files changed, 54 insertions(+), 44 deletions(-)
diff --git a/knapsack.c b/knapsack.c
@@ -5,16 +5,18 @@
#include "util.h"
int
-knapsack_bell(unsigned int k, unsigned int w, int m[k], int c[k], int out[k])
+knapsack_bell(unsigned int k, unsigned int w,
+ unsigned int m[k], unsigned int c[k],
+ BitChunk out[k/64+1])
{
- int (*opt)[w+1] = malloc(sizeof(*opt) * (k+1));
+ unsigned int (*opt)[w+1] = malloc(sizeof(*opt) * (k+1));
if (!opt) {
errno = ENOMEM;
return -1;
}
for (unsigned int i = 0; i <= k; ++i) {
- for (int wi = 0; wi <= w; ++wi) {
+ for (unsigned int wi = 0; wi <= w; ++wi) {
if (i == 0 || wi == 0)
opt[i][wi] = 0;
else if (m[i-1] > wi)
@@ -28,21 +30,13 @@ knapsack_bell(unsigned int k, unsigned int w, int m[k], int c[k], int out[k])
}
}
- unsigned int idx = 0;
for (; k > 0; --k) {
if (opt[k][w] != opt[k-1][w]) {
- out[idx++] = k - 1;
+ SET(out, k - 1);
w -= m[k-1];
}
}
- out[idx] = -1;
- for (unsigned int ogidx = --idx, temp; idx > ogidx/2; --idx) {
- temp = out[idx];
- out[idx] = out[ogidx-idx];
- out[ogidx-idx] = temp;
- }
-
free(opt);
}
@@ -50,9 +44,9 @@ static void
sift_down(unsigned int n, float a[n], unsigned int idx[n], unsigned int root)
{
while (1) {
- int left = 2 * root + 1;
- int right = left + 1;
- int largest = root;
+ unsigned int left = 2 * root + 1;
+ unsigned int right = left + 1;
+ unsigned int largest = root;
if (left < n && a[left] > a[largest])
largest = left;
@@ -99,25 +93,25 @@ extract_max(unsigned int *n, float a[*n], unsigned int idx[*n])
}
int
-knapsack_greed(unsigned int k, unsigned int w, int m[k], int c[k], int out[k])
+knapsack_greed(unsigned int k, unsigned int w,
+ unsigned int m[k], unsigned int c[k],
+ BitChunk out[k/64+1])
{
- unsigned int *indices = malloc(sizeof(*indices) * k);
float *density = malloc(sizeof(*density) * k);
- if (!indices || !density) {
+ if (!density) {
errno = ENOMEM;
return -1;
}
for (unsigned int i = 0; i < k; ++i) {
- indices[i] = i;
density[i] = (float)c[i]/m[i];
+ c[i] = i; /* reuse c array for indices */
}
unsigned int heap_size = k;
- heap_build(heap_size, density, indices);
+ heap_build(heap_size, density, c);
- unsigned int out_len = 0;
unsigned long weight = 0; /* weight can be larger than w - use long */
while (heap_size > 0) {
- unsigned int pos = extract_max(&heap_size, density, indices);
+ unsigned int pos = extract_max(&heap_size, density, c);
if (pos == UINT_MAX)
break;
@@ -125,18 +119,18 @@ knapsack_greed(unsigned int k, unsigned int w, int m[k], int c[k], int out[k])
if (weight > w)
weight -= m[pos];
else if (weight < w)
- out[out_len++] = pos;
+ SET(out, pos);
else
break;
}
- out[out_len] = -1;
- free(indices);
free(density);
}
int
-knapsack_full(unsigned int k, unsigned int w, int m[k], int c[k], int out[k])
+knapsack_full(unsigned int k, unsigned int w,
+ unsigned int m[k], unsigned int c[k],
+ BitChunk out[k/64+1])
{
if (k > sizeof(long)*8) {
errno = ERANGE;
@@ -156,12 +150,9 @@ knapsack_full(unsigned int k, unsigned int w, int m[k], int c[k], int out[k])
if (cost > best_cost) {
best_cost = cost;
- unsigned int out_len = 0;
- for (unsigned int i = 0; i < k; ++i) {
- if (list & (1UL << i))
- out[out_len++] = i;
+ out[0] = list; /* this function is not used above 64
+ - abuse this fact */
}
- out[out_len] = -1;
}
}
}
diff --git a/knapsack.h b/knapsack.h
@@ -1,3 +1,15 @@
-int knapsack_bell(unsigned int k, unsigned int w, int m[k], int c[k], int out[k]);
-int knapsack_greed(unsigned int k, unsigned int w, int m[k], int c[k], int out[k]);
-int knapsack_full(unsigned int k, unsigned int w, int m[k], int c[k], int out[k]);
+#include <stdint.h>
+typedef uint64_t BitChunk;
+#define CHECK(arr, bit) ((arr)[(bit/64)] & (1ULL << ((bit)%64)))
+#define SET(arr, bit) ((arr)[(bit/64)] |= (1ULL << ((bit)%64)))
+#define CLEAR(arr, bit) ((arr)[(bit/64)] &= ~(1ULL << ((bit)%64)))
+
+int knapsack_bell(unsigned int k, unsigned int w,
+ unsigned int m[k], unsigned int c[k],
+ BitChunk out[k/64+1]);
+int knapsack_greed(unsigned int k, unsigned int w,
+ unsigned int m[k], unsigned int c[k],
+ BitChunk out[k/64+1]);
+int knapsack_full(unsigned int k, unsigned int w,
+ unsigned int m[k], unsigned int c[k],
+ BitChunk out[k/64+1]);
diff --git a/knapsack_single.c b/knapsack_single.c
@@ -32,24 +32,31 @@ int
main(int argc, char *argv[])
{
argv0 = argv[0];
- unsigned int k = input(0, UINT_MAX),
- w = input(0, UINT_MAX);
- int *m = emalloc(sizeof(*m) * k),
+ unsigned int k = input(0, UINT_MAX);
+ unsigned int w = input(0, UINT_MAX),
+ *m = emalloc(sizeof(*m) * k),
*c = emalloc(sizeof(*c) * k);
unsigned int len;
for (len = 0; len < k; ++len)
- m[len] = input(0, INT_MAX);
+ m[len] = input(0, UINT_MAX);
for (len = 0; len < k; ++len)
- c[len] = input(0, INT_MAX);
+ c[len] = input(0, UINT_MAX);
- int *out = emalloc(sizeof(*out) * k);
+ BitChunk *out = ecalloc(sizeof(*out) * (k/64 + 1));
clock_t solve_time = clock();
if (knapsack(k, w, m, c, out) < 0)
eprintf("knapsack:");
solve_time = clock() - solve_time;
printf("%f\n", (double)solve_time / CLOCKS_PER_SEC);
- for (len = 0; len + 1 < k && out[len+1] > 0; ++len)
- printf("%d ", out[len]);
- printf("%d\n", out[len]);
+ long saved_number = -1;
+ for (len = 0; len + 1 < k; ++len) {
+ if (CHECK(out, len)) {
+ if (saved_number >= 0)
+ printf("%d ", saved_number);
+ saved_number = len;
+ }
+ }
+ if (saved_number >= 0)
+ printf("%d\n", saved_number);
}
diff --git a/sort.c b/sort.c
@@ -15,7 +15,7 @@ bubble_sort(unsigned int n, int a[n])
}
void
-choice_sort(unsigned int n, int a[n]) /* it's actually insertion_sort :nerd: */
+choice_sort(unsigned int n, int a[n]) /* it's actually selection_sort :nerd: */
{
int tmp;
for (unsigned int i = 0; i < n - 1; ++i) {
