#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Structure pour représenter un objet
struct Objet {
    int poids;
    int valeur;
    double ratio; // Rapport valeur/poids
};

// Fonction pour comparer deux objets en fonction de leur ratio valeur/poids
int comparer(const void *a, const void *b) {
    const struct Objet *objetA = (const struct Objet *)a;
    const struct Objet *objetB = (const struct Objet *)b;

    // Si le ratio de l'objet B est supérieur à celui de l'objet A, retourner 1, sinon retourner -1
    if (objetB->ratio > objetA->ratio) {
        return 1;
    } else {
        return -1;
    }
}

int maximum(int a, int b) {
    return (a >= b) ? a : b;
}

// Fonction récursive pour explorer toutes les combinaisons d'objets possibles
void explorerSolutions(int poids_sac, struct Objet objets[], int K[], int n, int poids_actuel, int solution[], int *solution_count, int index, bool *solutions_seen) {
    if (poids_actuel == poids_sac) {
        // Nous avons atteint le poids maximal du sac à dos, ajouter cette solution à la liste des solutions
        bool doublon = false;
        for (int i = 0; i < *solution_count; i++) {
            bool identique = true;
            for (int j = 0; j < n; j++) {
                if (solution[i * n + j] != solution[j]) {
                    identique = false;
                    break;
                }
            }
            if (identique) {
                doublon = true;
                break;
            }
        }
        if (!doublon) {
            for (int i = 0; i < n; i++) {
                solutions_seen[*solution_count * n + i] = solution[i]; // Copier la solution actuelle
            }
            (*solution_count)++;
        }
        return;
    }

    if (index == n) {
        return; // Si nous avons examiné tous les objets, retourner
    }

    // Inclure l'objet actuel dans la solution et passer à l'objet suivant
    for (int i = 0; i <= poids_sac / objets[index].poids; i++) {
        int poids_total = poids_actuel + objets[index].poids * i;
        if (poids_total <= poids_sac && K[poids_total] == K[poids_actuel] + objets[index].valeur * i) {
            solution[index] = i;
            // Créer une nouvelle solution pour l'appel récursif suivant
            int *new_solution = (int *)malloc(sizeof(int) * n);
            for (int j = 0; j < n; j++) {
                new_solution[j] = solution[j];
            }
            explorerSolutions(poids_sac, objets, K, n, poids_total, new_solution, solution_count, index + 1, solutions_seen);
            free(new_solution);
        }
    }
}
// Fonction pour afficher toutes les solutions optimales possibles
void afficherSolutions(int poids_sac, struct Objet objets[], int K[], int n) {
    int solution_count = 0;
    int *solution = (int *)malloc(sizeof(int) * n);
    bool *solutions_seen = (bool *)calloc(n * n * n, sizeof(bool));

    explorerSolutions(poids_sac, objets, K, n, 0, solution, &solution_count, 0, solutions_seen);

    printf("Solutions optimales:\n");
    for (int i = 0; i < solution_count; i++) {
        printf("{");
        for (int j = 0; j < n; j++) {
            printf("%d", solution[j]);
            if (j != n - 1) {
                printf(",");
            }
        }
        printf("}\n");
    }

    free(solution);
    free(solutions_seen);
}

void sacADos(int poids_sac, struct Objet objets[], int n) {
    // Tri des objets en fonction du rapport valeur/poids
    qsort(objets, n, sizeof(struct Objet), comparer);

    // Tableau pour stocker les valeurs maximales
    int K[poids_sac + 1];
    K[0] = 0;

    // Initialisation du tableau K
    for (int i = 1; i <= poids_sac; i++) {
        K[i] = 0;
    }

    // Recherche dynamique
    for (int i = 0; i < n; i++) {
        for (int j = poids_sac; j >= objets[i].poids; j--) {
            K[j] = maximum(K[j], objets[i].valeur + K[j - objets[i].poids]);
        }
    }

    // Affichage de la valeur maximale
    printf("La valeur maximale de ce probleme de sac a dos: %d\n", K[poids_sac]);

    // Affichage de toutes les solutions optimales
    afficherSolutions(poids_sac, objets, K, n);
}

int main() {
    int n, poids_sac;
    printf("Entrez le nombre d'objet(s): ");
    scanf("%d", &n);
    printf("Entrez la capacite du sac a dos: ");
    scanf("%d", &poids_sac);

    // Allocation dynamique d'un tableau d'objets
    struct Objet *objets = (struct Objet *)malloc(n * sizeof(struct Objet));

    printf("Entrez le poids et la valeur de chaque objet:\n");
    for (int i = 0; i < n; i++) {
        printf("Objet %d:\n", i + 1);
        printf("Poids: ");
        scanf("%d", &objets[i].poids);
        printf("Valeur: ");
        scanf("%d", &objets[i].valeur);
        objets[i].ratio = (double)objets[i].valeur / objets[i].poids; // Calcul du rapport valeur/poids
    }

    // Appel de la fonction sacADos
    sacADos(poids_sac, objets, n);

    // Libération de la mémoire allouée pour le tableau d'objets
    free(objets);

    return 0;
}