算法作业

dknap.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 128

int max(int a, int b) {
	return a > b ? a : b;
}

void DKnap(int p[], int w[], int n, int M) {
	int F[MAXN], P[MAXN], W[MAXN], l, h, next;
	F[0] = 1;
	P[1] = W[1] = 0;	// S^0 = { (0, 0) }
	l = h = 1;			// S^i_l .. S^i_h
	F[1] = next = 2;	// prepare for S^1
	for (int i = 1; i <= n; ++i) {
		int k = l, _max = 0, u = l;
		for (int r = l; r <= h; ++r) {
			if (W[r] + w[i] <= M && W[r] + w[i] > _max) {
				_max = W[r] + w[i];
				u = r;
			}
		}
		for (int j = l; j <= u; ++j) {
			int pp = P[j] + p[i];
			int ww = W[j] + w[i];
			while (k <= h && W[k] <= ww) {
				P[next] = P[k];
				W[next] = W[k];
				next++, k++;
			}
			if (k <= h && W[k] == ww) {
				pp = max(pp, P[k]);
				k++;
			}
			if (pp > P[next - 1]) {
				P[next] = pp;
				W[next] = ww;
				next++;
			}
			while (k <= h && P[k] <= P[next - 1]) {
				k++;
			}
		}
		while (k <= h) {
			P[next] = P[k];
			W[next] = W[k];
			next++, k++;
		}
		l = h + 1;
		h = next - 1;
		F[i+1] = next;
	}
	#if 0
	for (int i = 0; i <= n; ++i) {
		printf("S%d: ", i);
		for (int j = F[i]; j < F[i + 1]; ++j) {
			printf(j == F[i] ? "{ (%d, %d)" : ", (%d, %d)", P[j], W[j]);
		}
		printf(" }\n");
	}
	#endif
	int pp = P[F[n + 1] - 1], ww = W[F[n + 1] - 1], X[MAXN];
	printf("=> (%d, %d) ", pp, ww);
	for (int i = n; i > 0; --i) {
		X[i] = 1;
		for (int j = F[i - 1]; j < F[i]; ++j) {
			if (pp == P[j] && ww == W[j]) {
				X[i] = 0;
				break;
			}
		}
		if (X[i]) {
			pp -= p[i];
			ww -= w[i];
		}
		printf(i == n ? "[ X%d=%d" : ", X%d=%d", i, X[i]);
	}
	printf(" ]\n");
}

void map_to_i(const char *s, int *t) {
	char msg[256]; strcpy(msg, s);
	int i = 0; t[i++] = 0;
	char *c = strtok(msg, " ");
	while (c != NULL) {
		t[i++] = atoi(c);
		c = strtok(NULL, " ");
	}
}

void solve(int n, char *sp, char *sw, int M) {
	printf("p: [ %s ]  w: [ %s ]  M: %d\n", sp, sw, M);
	int p[MAXN], w[MAXN];
	map_to_i(sp, p);
	map_to_i(sw, w);
	DKnap(p, w, n, M);
}

int main(void) {
	solve(3, "1 2 5", "2 3 4", 6);
	solve(4, "2 5 8 1", "10 15 6 9", 32);
	solve(6, "100 50 20 10 7 3", "100 50 20 10 7 3", 165);
	return 0;
}

greedy_job.c

#include <stdio.h>

int greedy_job(int d[], int j[], int n) {
	int t = 0, k = 0;
	for (int i = 0; i < n; ++i) {
		if (t + 1 <= d[i]) {
			j[k++] = i;
			++t;
		}
	}
	return k;
}

int main(void) {
	int d[256], j[256], n, i;
	// puts("input <n>, then n <d[i]>s sort by p[i] desc,
	// it returns sel(a, 0, n-1, i)");
	scanf("%d", &n);
	if (n < 0 || n >= 256) return 1;
	for (i = 0; i < n; ++i) scanf("%d", &d[i]);
	n = greedy_job(d, j, n);
	for (i = 0; i < n; ++i)
		printf(i ? " %d" : "%d", j[i]);
	putchar('\n');
}

kruskal.c

#include <stdio.h>

void Union(int parent[], int i, int j) {
	int x = parent[i] + parent[j];
	if (parent[i] < parent[j])
		parent[parent[j] = i] = x;
	else
		parent[parent[i] = j] = x;
}

int Find(int parent[], int i) {
	while (parent[i] > 0)
		i = parent[i];
	return i;
}

void add_edge(double cost[128][128], int i, int j, double c) {
	cost[i][j] = cost[j][i] = c;
}

double min_edge(double cost[128][128], int n, int ret[2]) {
	double mincost = -1.0;
	for (int i = 0; i < n - 1; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (cost[i][j] < 0) continue;
			if (mincost < 0 || mincost > cost[i][j]) {
				mincost = cost[i][j];
				ret[0] = i;
				ret[1] = j;
			}
		}
	}
	return mincost;
}

void del_edge(double cost[128][128], int i, int j) {
	cost[i][j] = cost[j][i] = -1.0;
}

double Kruskal(double cost[128][128], int parent[], int n) {
	int i, ret[2];
	double mincost = .0;
	for (i = 0; i < n; ++i)
		parent[i] = -1;
	for (i = 0; i < n - 1;) {
		double _mincost = min_edge(cost, n, ret);
		if (_mincost < 0) break;
		del_edge(cost, ret[0], ret[1]);
		int j = Find(parent, ret[0]), k = Find(parent, ret[1]);
		if (j != k) {
			++i;
			mincost += _mincost;
			Union(parent, j, k);
			#if 0
			printf("%d-[%.1lf]-%d >> T | ", j, _mincost, k);
			for (int i = 0; i < 6; ++i)
				printf(i ? ", %2d" : "parent = [ %2d", parent[i]);
			puts(" ]");
			#endif
		}
	}
	if (i != n - 1)
		return -1.0;
	return mincost;
}

int parent[128];
double cost[128][128];
int main(void) {
	for (int i = 0; i < 128; ++i)
		for (int j = 0; j < 128; ++j)
			cost[i][j] = -1.0;
	add_edge(cost, 0, 1, 10.0);
	add_edge(cost, 0, 5, 45.0);
	add_edge(cost, 0, 3, 30.0);
	add_edge(cost, 1, 2, 50.0);
	add_edge(cost, 1, 4, 40.0);
	add_edge(cost, 1, 5, 45.0);
	add_edge(cost, 2, 4, 25.0);
	add_edge(cost, 2, 5, 15.0);
	add_edge(cost, 3, 5, 20.0);
	add_edge(cost, 4, 5, 15.0);
	double mincost = Kruskal(cost, parent, 6);
	if (mincost < 0) {
		puts("no spanning tree");
		return 1;
	}
	printf("mincost = %.1lf  ", mincost);
	for (int i = 0; i < 6; ++i)
		printf(i ? ", %d" : "parent = [ %d", parent[i]);
	puts(" ]");
	return 0;
}

select2.c

#include <stdio.h>
#include <limits.h>

const int r = 5;

void swap(int a[], int i, int j) {
	int t = a[i];
	a[i] = a[j];
	a[j] = t;
}

void insert_sort(int a[], int beg, int end) {
	for (int i = beg + 1; i <= end; ++i) {
		for (int j = i; j > beg; --j) {
			if (a[j] < a[j - 1]) {
				swap(a, j, j - 1);
			}
		}
	}
}

int partition(int a[], int m, int p) {
	int i = m, v = a[m];
	while (i < p) {
		do { ++i; } while (a[i] < v);
		do { --p; } while (a[p] > v);
		if (i < p) swap(a, i, p);
	}
	a[m] = a[p];
	a[p] = v;
	return p;
}

int sel(int a[], int m, int p, int k) {
	int n, i, j;
	while (1) {
		n = p - m + 1;
		if (n <= r) {
			insert_sort(a, m, p);
			return m + k - 1;
		}
		int o = n / r;
		for (i = 1; i < o; ++i) {
			insert_sort(a, m + (i - 1) * r, m + i * r - 1);
			swap(a, m + i - 1, m + (i - 1) * r + r / 2 - 1);
		}
		j = sel(a, m, m + o - 1, (o + 1) / 2);
		swap(a, m, j);
		j = partition(a, m, p + 1);
		if (j - m + 1 == k)
			return j;
		else if (j - m + 1 > k)
			p = j - 1;
		else {
			k -= j - m + 1;
			m = j + 1;
		}
	}
}

int main(void) {
	int n, i, j, a[256];
	// puts("input <n>, then <n numbers>, then <i>, it returns sel(a, 0, n-1, i)");
	scanf("%d", &n);
	if (n < 0 || n >= 256) return 1;
	for (i = 0; i < n; ++i) scanf("%d", &a[i]);
	while (scanf("%d", &i) != EOF) {
		i = sel(a, 0, n - 1, i);
		for (j = 0; j < n; ++j) printf(j ? " %d" : "%d", a[j]);
		printf(" -> %d\n", i);
	}
	return 0;
}