Code:
#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);
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;
}
wcType *r = (wcType*)malloc(n*sizeof(wcType)); , is it right?