#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include <sys/time.h>

#define MAX_NUM_OBJ 100

int num_obj = 0;
int capacity;
int weight[MAX_NUM_OBJ];
int utility[MAX_NUM_OBJ];

void read_problem(char *filename){
  char line[256];

  FILE *problem = fopen(filename,"r");
  if (problem == NULL){
    fprintf(stderr,"File %s not found.\n",filename);
    exit(-1);
  }

  while (fgets(line, 256, problem) != NULL){
    switch(line[0]){
    case 'c': // capacity
      if (sscanf(&(line[2]),"%d\n", &capacity) != 1){
	fprintf(stderr,"Error in file format in line:\n");
	fprintf(stderr, "%s", line);
	exit(-1);
      }
      break;

    case 'o': // graph size
      if (num_obj >= MAX_NUM_OBJ){
	fprintf(stderr,"Too many objects (%d): limit is %d\n", num_obj, MAX_NUM_OBJ);
	exit(-1);
      }
      if (sscanf(&(line[2]),"%d %d\n", &(weight[num_obj]), &(utility[num_obj])) != 2){
	fprintf(stderr,"Error in file format in line:\n");
	fprintf(stderr, "%s", line);
	exit(-1);
      }
      else
	num_obj++;
      break;

    default:
      break;
    }
  }
  if (num_obj == 0){
    fprintf(stderr,"Could not find any object in the problem file. Exiting.");
    exit(-1);
  }

}
int max(int x, int y){
    if (x >= y) return x;
    else return y;
}

int min(int x, int y){
    if (x >= y) return y;
    else return x;
}

int capacite(int ** S, int * M, int N, int j){
    int u = S[0][j];
    int somme;
    int m;
    if (u != 0) {
        somme = M[0];
        m = M[0];
    }
    else {
        somme = 0;
        m = 0;
    }
    for (int i=0; i<N-1; i++){
        if (m < S[i+1][j]) {
            somme += M[i+1];
        }
        m = M[i+1];
    }
    return somme;
}

int ** matUtiliteMax(int * M, int * U, int N, int c){

    // Création matrice s
    int ** S = malloc(N*sizeof(int*));
    for (int i=0; i<N; i++)
        S[i] = malloc((c+1)*sizeof(int));

    // Remplissage première ligne
    for (int j=0; j<c+1; j++){
        if (M[0] <= j) S[0][j] = U[0];
        else S[0][j] = 0;
    }

    // Remplissage des lignes 1 à N
    for (int i=1; i<N; i++){
        for (int j=0; j<c+1; j++){
            if (j >= M[i]){
                if ((S[i-1][j-M[i]] + U[i])-S[i-1][j] >= 0){
                    S[i][j] = S[i-1][j-M[i]] + U[i];
                }
                else S[i][j] = S[i-1][j];
            }

            else S[i][j] = S[i-1][j];
        }
    }

    return S;

}

int * utilityMax(int ** S, int * Poid, int * utilite, int nbl, int nbc){
    int * E = malloc(nbl*sizeof(int));
    for(int i = 0; i<nbl; i++) E[i] = 0;
    int j = nbc;
    int i = nbl - 1;
    int itmp = nbl - 1;
    int jtmp = nbc;
    while (j > 0 && i > 0){
        if (S[i][j] > S[i-1][j]) E[i] = 1;
        i -= 1;
        while ((S[i][j] != (S[itmp][jtmp] - Poid[itmp])) && j > 0) {
            j -= 1;
        }
        itmp = i;
        jtmp = j;
    }
    return E;
}

void afficherMat(int ** mat, int nbl, int nbc){
    for (int i = 0; i<nbl; i++){
        for (int j = 0; j<nbc; j++){
            printf(" %d |",mat[i][j]);
        }
        printf("\n");
    }
}

void afficherTab(int * tab, int nbc){
    for (int j = 0; j<nbc; j++){
        printf(" %d |",tab[j]);
    }
}

void main(int argc, char * argv[]){
    read_problem(argv[1]);
    int ** S = matUtiliteMax(weight,utility,num_obj,capacity);
    /*afficherMat(S, num_obj, capacity);*/
    int * E = malloc(num_obj*sizeof(int));
    for(int i = 0; i<num_obj; i++) E[i] = 0;
    int j = capacity;
    int i = num_obj - 1;
    int itmp = num_obj - 1;
    int jtmp = capacity;
    while (j > 0 && i > 0){
        if (S[itmp][jtmp] > S[i-1][j]){
            E[i] = 1;
            itmp = i;
            while ((S[i][j] != (S[itmp][jtmp] - utility[itmp])) && j > 0) {
                j -= 1;
            }
        }
        i -= 1;
        itmp = i;
        jtmp = j;
    }
    afficherTab(E,num_obj);
}