#include #include #include typedef struct { double price; double apprate; } item; #define INFINITY 1e256 item *genitems ( int n ) { item *A; int i; A = (item *)malloc(n * sizeof(item)); for (i=0; i 12) { fprintf(stderr, "*** n is too large, skipping exhaustive search\n"); return NULL; } P = (int *)malloc(n * sizeof(int)); Q = (int *)malloc(n * sizeof(int)); for (i=0; i maxcost) { maxcost = cost; k = j; } } } S[i] = k; bought[k] = 1; } free(bought); return S; } int *grdsearch2 ( item *A, double **R, int n ) { int *S, *bought, i, j, k; double cost, mincost; S = (int *)malloc(n * sizeof(int)); bought = (int *)malloc(n * sizeof(int)); for (i=0; i=0; --i) { mincost = INFINITY; k = -1; for (j=0; j maxincr) { maxincr = incr; k = j; } } } } S[i] = k; bought[k] = 1; } free(bought); return S; } /* This implements the minimum price increase last heuristic */ int *grdsearch4 ( item *A, double **R, int n ) { int *S, *bought, i, j, k; double incr, minincr; S = (int *)malloc(n * sizeof(int)); bought = (int *)malloc(n * sizeof(int)); for (i=0; i=0; --i) { k = -1; if (i == 0) { for (j=0; j 1) n = atoi(argv[1]); else scanf("%d", &n); printf("n = %d\n", n); srand((unsigned int)time(NULL)); A = genitems(n); R = genallrates(A,n); printf("\n+++ Greedy search 1\n"); S = grdsearch1(A,R,n); printseq(A,R,S,n); free(S); printf("\n+++ Greedy search 2\n"); S = grdsearch2(A,R,n); printseq(A,R,S,n); free(S); printf("\n+++ Greedy search 3\n"); S = grdsearch3(A,R,n); printseq(A,R,S,n); free(S); printf("\n+++ Greedy search 4\n"); S = grdsearch4(A,R,n); printseq(A,R,S,n); free(S); printf("\n+++ Exhaustive search\n"); S = exhsearch(A,R,n); if (S) { printseq(A,R,S,n); free(S); } exit(0); }