#include <stdio.h>
#include <stdlib.h>
#define N 100

/**
Ce code permet de resoudre le probleme de sac a dos ( 0,1,2,.....N) en utilisant la programmation dynamique et une approche récursive.
 Il commence par lire les données d'entrée, à savoir le nombre d'objets et la capacité maximale du sac à dos,
  ainsi que les poids et les valeurs de chaque objet.
  Ensuite, il calcule la valeur maximale que l'on peut obtenir en remplissant le sac à dos selon les poids et les valeurs des objets donnés.
   Cette valeur maximale est calculée en utilisant un tableau dynamique et en itérant sur chaque objet et chaque poids possible du sac à dos
   pour choisir la meilleure combinaison. Enfin, le programme affiche toutes les combinaisons optimales d'objets qui donnent la valeur maximale,
    en utilisant une approche récursive pour explorer toutes les possibilités.
 */

// Fonction pour trouver le maximum entre deux entiers
int maximum(int a, int b) {
    if (a >= b) {
        return a;
    } else {
        return b;
    }
}

// Fonction pour vérifier l'existence d'une solution dans un ensemble de solutions
int existence_solution(int solutionSet[][N], int n, int* setIndex, int count[], int taille_solution) {
    int i, j;
    // Parcourir l'ensemble de solutions
    for (i = 0; i < *setIndex; i++) {
        int trouve = 1;
        // Vérifier si la solution actuelle correspond à la solution donnée
        for (j = 0; j < taille_solution; j++) {
            if (solutionSet[i][j] != count[j]) {
                trouve = 0;
                break;
            }
        }
        // Si la solution est trouvée, retourner vrai
        if (trouve) {
            return 1;
        }
    }
    // Si la solution n'est pas trouvée, retourner faux
    return 0;
}

// Fonction pour afficher les solutions optimales du problème du sac à dos
void afficherSolutions(int W, int poids[], int valeur[], int K[], int n, int count[], int solutionSet[][N], int* setIndex) {
    // Cas de base : poids actuel est 0
    if (W == 0) {
        // Vérifier si cette solution existe déjà dans l'ensemble
        if (existence_solution(solutionSet, n, setIndex, count, n)) {
            return;
        }
        // Ajouter la solution à l'ensemble
        for (int i = 0; i < n; i++) {
            solutionSet[*setIndex][i] = count[i];
        }
        (*setIndex)++;

        // Afficher la solution
        printf("{");
        for (int i = 0; i < n; i++) {
            printf("%d", count[i]);
            if (i != n - 1) {
                printf(",");
            }
        }
        printf("}\n");
    } else {
        // Boucler à travers les objets disponibles
        for (int i = 0; i < n; i++) {
            // Vérifier si l'objet peut être inclus dans le sac
            if (poids[i] <= W && K[W] == valeur[i] + K[W - poids[i]]) {
                count[i]++;
                // Appel récursif pour explorer d'autres possibilités
                afficherSolutions(W - poids[i], poids, valeur, K, n, count, solutionSet, setIndex);
                count[i]--;
            }
        }
    }
}

// Fonction principale pour résoudre le problème du sac à dos
int sacADos(int poids_sac, int poids[], int valeur[], int n, int count[]) {
    int i, weight;
    int K[poids_sac + 1];

    // Initialisation de la première valeur de la table K
    K[0] = 0;

    // Remplissage de la table K avec les valeurs optimales
    for (weight = 1; weight <= poids_sac; weight++) {
        K[weight] = 0;
        for (i = 0; i < n; i++) {
            if (poids[i] <= weight) {
                // Calcul de la valeur optimale pour le poids donné
                K[weight] = maximum(K[weight], valeur[i] + K[weight - poids[i]]);
            }
        }
    }

    // Déclaration d'un ensemble pour stocker les solutions
    int solutionSet[N][N];
    int setIndex = 0;

    // Affichage des solutions optimales
    printf("Solutions optimales:\n");
    afficherSolutions(poids_sac, poids, valeur, K, n, count, solutionSet, &setIndex);
    printf(" La valeur maximale de ce probleme de sac a dos: %d\n", K[poids_sac]);

    return K[poids_sac];
}

// Fonction principale du programme
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);
    int poids[n], valeur[n], count[n];
    printf("-----------------------------------***** S A C     A     D O S *****---------------------------------------\n");
    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", &poids[i]);
        printf(" la valeur de l'objet '%d': ",i+1);
        scanf("%d", &valeur[i]);
        count[i] = 0;
    }
    int res = sacADos(poids_sac, poids, valeur, n, count);

    return 0;
}