001: #include<stdio.h>
002: #include<stdlib.h>
003: 
004: // main function prototypes
005: int *read_sequence(int *, int *);
006: void check_superincreasing(const int, const int *);
007: void greedy(int, int, int *);
008: 
009: int main(int argc, char **argv){
010: 
011:   // variables to store number of elements and backpack size
012:   int n, z;
013: 
014:   // variable for managing an array of int
015:   int *seq;
016:    
017:   // call function that ask a file name, read and store it
018:   // the function fills z and n, and returns the address of a dinamically allocated array of ints
019:   seq = read_sequence(&z, &n);
020: 
021:   // call functikn that check the superincreasing requirement, that function terminates the program whether the
022:   // sequence is not a superincreasing one
023:   // int takes as input the array and the number of elements
024:   //it does not modify anything and therefore we can pass arguments as constant ones
025:   check_superincreasing(n, seq);
026: 
027:   // call function that fills the "backpack" using the explained greedy algorithm
028:   greedy(z, n, seq);
029: 
030:   free(seq); // free dinamically allocated memory
031: 
032: 
033: 
034:   return 0;
035: }
036: 
037: // comparison function for qsort()
038: int ord(const void *a, const void *b){
039:   int na = *((int *)a);
040:   int nb = *((int *)b);
041: 
042:   return na - nb;
043: }
044: 
045: // this function takes as input the addresses where to write the size of the backpack and how many object to store we have
046: // it returns the address of a dynamically allocated array of ints
047: int *read_sequence(int *backpack_size, int *nmemb)
048: {
049: 
050:   char tmp[1000];
051:   printf("Please, enter file name: ");
052:   scanf(" %s", tmp);
053: 
054:   FILE *x = fopen(tmp, "rb"); // "rb" for binary files
055:   if(!x)
056:   {
057:     perror("");
058:     exit(EXIT_FAILURE);
059:   }
060: 
061:   fread(backpack_size, sizeof(int), 1, x); // read first 4 bytes (namely, an int) and store them at the backpack_size address
062:   fread(nmemb,     sizeof(int), 1, x);     // read an int and store it at nmemb address
063: 
064:   int *arr = malloc(sizeof(int)* *nmemb);   // allocate space for the array
065:   fread(arr,       sizeof(int), *nmemb, x); // read data into the array
066:   fclose(x);
067: 
068:   qsort(arr, *nmemb, sizeof(int), ord);    // sort the array
069: 
070:   // print the data we put in the array, their number, and the backpack size
071:   printf("Backpack size = %d, num. of obj. = %d, values: \n", *backpack_size, *nmemb);
072:   for(int i = 0; i < *nmemb; ++i)
073:     printf("%d ", arr[i]);
074:   printf("\n");
075: 
076:   return arr;
077: }
078: 
079: // this function takes as input the array and the number of elements in the array
080: // and check whether the sequence of numbers in the array is a superincreasing one
081: // namely it looks if every element of the sequence is greater than the sum of all 
082: // previous elements
083: // it is assuming that the number in the sequence are sorted for the smallest to 
084: // the biggest
085: void check_superincreasing(const int n, const int *seq)
086: {
087: 
088:   // accumulator for computing the sum of elements already considered
089:   int sum = 0;
090:   for(int i = 0; i < n; ++i)
091:   {
092:     if(seq[i] <= sum)
093:     {
094:       printf("The sequence is not a superincreasing one, exiting.\n");
095:       exit(EXIT_FAILURE);
096:     }
097: 
098:     sum += seq[i];
099:   }
100: }
101: 
102: // this function takes as input the array (seq), the number of elements in the array (n)
103: // and the size (z) of the backpack
104: void greedy(int z, int n, int *seq)
105: {
106:   double orig_space = z;
107: 
108:   // consider every element in the array from the greatest one up to the smallest one
109:   for(int i = n - 1; i >= 0; --i)
110:   {
111:     if(seq[i] <= z) // if the element fits in the backpack we can insert it. Namely, we reduce the available space
112:       z -= seq[i];
113:     else
114:       seq[i] = 0; // "remove" from the sequence the elements that we can not put into the backpack
115:   }
116:   // at the end of this cycle, z contains the free space in the backpack. And, in the array,
117:   // the only elements != 0 are the one we were able to insert in the backpack
118: 
119:   // print only elements that are !=0
120:   printf("The following elements are in the backpack: ");
121:   for(int i = 0; i < n; ++i)
122:   {
123:     if(seq[i] != 0)
124:       printf("%d + ", seq[i]);
125:   }
126:   // compute and print the filling ratio
127:   printf("The backpack has been filled to %g%%\n", (orig_space - z)/orig_space*100);
128: 
129: }
130: 
131: