commit 053934bc19eebd3b7cb44312d451cfe8789d4dd4
Author: Plat <plat@stellar-nexus.ru>
Date: Tue, 25 Nov 2025 00:23:51 +0000
Initial commit
Diffstat:
| A | Makefile | | | 26 | ++++++++++++++++++++++++++ |
| A | knapsack.c | | | 167 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | knapsack.h | | | 3 | +++ |
| A | knapsack_single.c | | | 56 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | sort.c | | | 57 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | sort.h | | | 4 | ++++ |
| A | sort_single.c | | | 51 | +++++++++++++++++++++++++++++++++++++++++++++++++++ |
7 files changed, 364 insertions(+), 0 deletions(-)
diff --git a/Makefile b/Makefile
@@ -0,0 +1,26 @@
+BIN1 =\
+ bell \
+ greed \
+ full
+
+BIN2 =\
+ bubble \
+ choice \
+ insert \
+ shell
+
+include config.mk
+
+
+all: ${BIN1} ${BIN2}
+
+${BIN1}:
+ ${CC} ${CFLAGS} ${LDFLAGS} -D"$@" knapsack_single.c knapsack.c -o "$@"
+ strip "$@"
+
+${BIN2}:
+ ${CC} ${CFLAGS} ${LDFLAGS} -D"$@" sort_single.c sort.c -o "$@"
+ strip "$@"
+
+clean:
+ rm -f ${BIN1} ${BIN2}
diff --git a/knapsack.c b/knapsack.c
@@ -0,0 +1,167 @@
+#include <errno.h>
+#include <limits.h>
+#include <stdlib.h>
+
+#include "util.h"
+
+int
+knapsack_bell(unsigned int k, unsigned int w, int m[k], int c[k], int out[k])
+{
+ 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) {
+ if (i == 0 || wi == 0)
+ opt[i][wi] = 0;
+ else if (m[i-1] > wi)
+ opt[i][wi] = opt[i-1][wi];
+ else
+ opt[i][wi] = MAX
+ (
+ opt[i-1][wi],
+ c[i-1] + opt[i-1][wi - m[i-1]]
+ );
+ }
+ }
+
+ unsigned int idx = 0;
+ for (; k > 0; --k) {
+ if (opt[k][w] != opt[k-1][w]) {
+ out[idx++] = 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);
+}
+
+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;
+
+ if (left < n && a[left] > a[largest])
+ largest = left;
+ if (right < n && a[right] > a[largest])
+ largest = right;
+
+ if (largest == root)
+ break;
+
+ float tmp = a[root];
+ a[root] = a[largest];
+ a[largest] = tmp;
+
+ unsigned int tmpi = idx[root];
+ idx[root] = idx[largest];
+ idx[largest] = tmpi;
+
+ root = largest;
+ }
+}
+
+static void
+heap_build(unsigned int n, float a[n], unsigned int idx[n])
+{
+ for (int i = n / 2 - 1; i >= 0; --i)
+ sift_down(n, a, idx, i);
+}
+
+static unsigned int
+extract_max(unsigned int *n, float a[*n], unsigned int idx[*n])
+{
+ if (*n == 0)
+ return UINT_MAX;
+
+ unsigned int max_index = idx[0];
+
+ --*n;
+ a[0] = a[*n];
+ idx[0] = idx[*n];
+
+ sift_down(*n, a, idx, 0);
+
+ return max_index;
+}
+
+int
+knapsack_greed(unsigned int k, unsigned int w, int m[k], int c[k], int out[k])
+{
+ unsigned int *indices = malloc(sizeof(*indices) * k);
+ float *density = malloc(sizeof(*density) * k);
+ if (!indices || !density) {
+ errno = ENOMEM;
+ return -1;
+ }
+ for (unsigned int i = 0; i < k; ++i) {
+ indices[i] = i;
+ density[i] = (float)c[i]/m[i];
+ }
+ unsigned int heap_size = k;
+ heap_build(heap_size, density, indices);
+
+ 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);
+ if (pos == UINT_MAX)
+ break;
+
+ weight += m[pos];
+ if (weight > w)
+ weight -= m[pos];
+ else if (weight < w)
+ out[out_len++] = 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])
+{
+ if (k > sizeof(long)*8) {
+ errno = ERANGE;
+ return -1;
+ }
+ unsigned long best_cost = 0;
+ for (unsigned long list = 0; list < (1UL << k); ++list) {
+ unsigned long weight = 0, cost = 0;
+ for (unsigned int i = 0; i < k; ++i) {
+ if (!(list & (1UL << i)))
+ continue;
+ weight += m[i];
+ if (weight > w)
+ break;
+ cost += c[i];
+ }
+
+ 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[out_len] = -1;
+ }
+ }
+}
diff --git a/knapsack.h b/knapsack.h
@@ -0,0 +1,3 @@
+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]);
diff --git a/knapsack_single.c b/knapsack_single.c
@@ -0,0 +1,56 @@
+#include <ctype.h>
+#include <limits.h>
+#include <stdio.h>
+#include <time.h>
+
+#include "knapsack.h"
+#include "util.h"
+
+#ifdef bell
+#define knapsack knapsack_bell
+#elif defined(greed)
+#define knapsack knapsack_greed
+#elif defined(full)
+#define knapsack knapsack_full
+#else
+#error You need to define either bell, greed, or full
+#endif
+
+static long long int
+input(long long mivnal, long long maxval)
+{
+ unsigned char len = 0, arr[UCHAR_MAX];
+
+ for (int c = getchar(); !isspace(c) && c != EOF; c = getchar())
+ arr[len++] = c;
+ arr[len] = '\0';
+ return estrtonum(arr, minval, maxval);
+
+}
+
+int
+main(void)
+{
+ unsigned int k = input(0, UINT_MAX),
+ w = input(0, UINT_MAX);
+ int *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);
+ for (len = 0; len < k; ++len)
+ c[len] = input(0, INT_MAX);
+ if (getchar() != EOF)
+ weprintf("More than %d numbers provided - ignoring them\n", k);
+
+ int *out = emalloc(sizeof(*out) * k);
+ clock_t solve_time = clock();
+ if (knapsack(k, w, m, c, out) < 0)
+ eprintf("knapsack:");
+ solve_time = clock() - solve_time;
+ printf("%f\n", 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]);
+}
diff --git a/sort.c b/sort.c
@@ -0,0 +1,57 @@
+void
+bubble_sort(unsigned int n, int a[n])
+{
+ int tmp;
+ for (unsigned int i = 0; i < n - 1; ++i) {
+ for (unsigned int j = 0; j < n - i - 1; ++j) {
+ if (a[j] > a[j+1]) {
+ tmp = a[j];
+ a[j] = a[j+1];
+ a[j+1] = tmp;
+ }
+ }
+ }
+
+}
+
+void
+choice_sort(unsigned int n, int a[n]) /* it's actually insertion_sort :nerd: */
+{
+ int tmp;
+ for (unsigned int i = 0; i < n - 1; ++i) {
+ int min = i;
+ for (unsigned int j = i + 1; j < n; ++j) {
+ if (a[j] < a[min])
+ min = j;
+ }
+ tmp = a[i];
+ a[i] = a[min];
+ a[min] = tmp;
+ }
+}
+
+void
+insert_sort(unsigned int n, int a[n])
+{
+ int key;
+ for (unsigned int i = 1; i < n; ++i) {
+ key = a[i];
+ for (unsigned int j = i - 1; j >= 0 && a[j] > key; --j)
+ a[j+1] = a[j];
+ a[j+1] = key;
+ }
+}
+
+void
+shell_sort(unsigned int n, int a[n])
+{
+ int tmp;
+ for (unsigned int gap = n/2; gap > 0; gap /= 2) {
+ for (unsigned int i = gap; i < n; ++i) {
+ tmp = a[i];
+ for (unsigned int j = i; j >= gap && a[j-gap] > tmp; j -= gap)
+ a[j] = a[j-gap];
+ a[j] = tmp;
+ }
+ }
+}
diff --git a/sort.h b/sort.h
@@ -0,0 +1,4 @@
+void bubble_sort(unsigned int n, int a[n]);
+void choice_sort(unsigned int n, int a[n]);
+void insert_sort(unsigned int n, int a[n]);
+void shell_sort(unsigned int n, int a[n]);
diff --git a/sort_single.c b/sort_single.c
@@ -0,0 +1,51 @@
+#include <ctype.h>
+#include <limits.h>
+#include <stdio.h>
+#include <time.h>
+
+#include "sort.h"
+#include "util.h"
+
+#ifdef bubble
+#define sort bubble_sort
+#elif defined(choice)
+#define sort choice_sort
+#elif defined(insert)
+#define sort insert_sort
+#elif defined(shell)
+#define sort shell_sort
+#else
+#error You need to define either bubble, choice, insert, or shell
+#endif
+
+static long long int
+input(long long mivnal, long long maxval)
+{
+ unsigned char len = 0, arr[UCHAR_MAX];
+
+ for (int c = getchar(); !isspace(c) && c != EOF; c = getchar())
+ arr[len++] = c;
+ arr[len] = '\0';
+ return estrtonum(arr, minval, maxval);
+
+}
+
+int
+main(void)
+{
+ unsigned int n = input(0, UINT_MAX),
+ int *arr = emalloc(sizeof(*arr) * n);
+
+ unsigned int len;
+ for (len = 0; len < n; ++len)
+ arr[len] = input(0, INT_MAX);
+ if (getchar() != EOF)
+ weprintf("More than %d numbers provided - ignoring them\n", n);
+
+ clock_t solve_time = clock();
+ sort(n, arr);
+ solve_time = clock() - solve_time;
+ printf("%f\n", solve_time / CLOCKS_PER_SEC);
+ for (len = 0; len < k; ++len)
+ printf("%d\n", out[len]);
+}
