#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define w_max 50
#define c_max 200 

typedef union wcStruct {
	float d;
	int index;
}*wcType;

void iexchange(int *a, int *b)
{
	int t = *a;
	*a = *b;
	*b = t;
}

void fexchange(float *a, float *b)
{
	float t = *a;
	*a = *b;
	*b = t;
}

int partition(wcType *a, int p, int r)
{
	float x = a[r]->d;
	int i, j;
	j = p-1;
	for (i = p; i < r; i++) {
		if (a[i]->d <= x) {
			j++;
			fexchange(&a[i]->d, &a[j]->d);
			iexchange(&a[i]->index, &a[j]->index);
		}
	}
	j++;
	fexchange(&a[j]->d, &a[r]->d);
	iexchange(&a[j]->index, &a[r]->index);
	return j;	
}

void quick_sort(wcType *a, int p, int r)
{
	int q;
	if (p < r) {
		q = partition(a, p, r);
		quick_sort(a, p, q-1);
		quick_sort(a, p+1, r);
	}
}

void knapsack_01(int *get, int *w, int *c, int m, int n)
{
	int sum, i;
	wcType *r = (wcType*)malloc(n*sizeof(wcType));
	for (i = 0; i < n; i++)
		get[i] = 0;
	for (i = 0; i < n; i++) {
		r[i]->d = c[i]/w[i];
		r[i]->index = i;
		printf("r[i]->d = %f, r[i]->index = %d\n", r[i]->d, r[i]->index);
		sum += w[i];
	}
	if (sum >= m) {
		free(r);
		for (i = 0; i < n; i++)
			get[i] = 1;
		return;
	}
	else {
		sum = 0;
		quick_sort(r, 0, n-1);
		for (i = 0; i < n; i++) {
			sum += w[r[i]->index];
			if (sum > m) break;
			get[i] = 1;
		}
	}
	free(r);
}

void generation(FILE *pFile, int *w, int *c, int m, int n)
{
	int i;
	srand(time(NULL));
	fprintf(pFile, "%d\n%d\n", m, n);
	for (i = 0; i < n; i++) {
		w[i] = rand()%w_max+1;
		c[i] = rand()%c_max+1;
	}
	for (i = 0; i < n; i++) {
		if (i%10 == 0) 
			fprintf(pFile, "\n");
		fprintf(pFile, "%d ", w[i]);
	}
	fprintf(pFile, "\n");
	for (i = 0; i < n; i++) {
		if (i%10 == 0)
			fprintf(pFile, "\n");
		fprintf(pFile, "%d ", c[i]);
	}
}

int main()
{
	int *w, *c, *get;  
	// w = weight, c = cost, get = which items have been got(1 = got, 0 = no got)
	int n, m, i;
	char gen;
	FILE *pFile;
	pFile = fopen("knapsack.dat", "wt");
	printf("m = ");
	scanf("%d", &m);
	printf("n = ");
	scanf("%d", &n);
	
	if (pFile) {
		w = (int*)malloc(n*sizeof(int));
		c = (int*)malloc(n*sizeof(int));
		get = (int*)malloc(n*sizeof(int));
		generation(pFile, w, c, m, n);
		fclose(pFile);
	}
	else {
		printf("Can't open file.\n");
		return;
	}
	knapsack_01(w, c, get, m, n);
	for (i = 0; i < n; i++)
		printf("%d ", get[i]);
	/*
	pFile = fopen("knapsack.out", "wt");
	if (pFile) {
	knapsack_01(w, c, d, n, size);
	for (i = 0; i < size; i++)
		fprintf(pFile, "%d ", w[d[i]]);
	fclose(pFile);
	}
	*/
	return 0;
}

[jeff@localhost ~]$ ./knapsack
m = 1
n = 1
r[i]->d = 0.000000, r[i]->index = 0
0 [jeff@localhost ~]$

 [jeff@localhost ~]$ ./knapsack
m = -1
n = 100
Segmentation fault

[jeff@localhost ~]$ ./knapsack
m = -1
n = -1

[jeff@localhost ~]$ ./knapsack
m = .0
Segmentation fault

[jeff@localhost ~]$ ./knapsack
m = a
Segmentation fault

[jeff@localhost ~]$ ./knapsack
m = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
n = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Segmentation fault

int sum, i;
	wcType *r = (wcType*)malloc(n*sizeof(wcType));
	for (i = 0; i < n; i++)
		get[i] = 0;
	for (i = 0; i < n; i++) {
		r[i]->d = c[i]/w[i];
		r[i]->index = i;
		printf("r[i]->d = %f, r[i]->index = %d\n", r[i]->d, r[i]->index);
		sum += w[i];