#include <stdio.h>
#include <stdlib.h>
#define N 100
int maximum(int a, int b) {
    if (a >= b) {
        return a;
    } else {
        return b;
    }
}
int existence_solution(int solutionSet[][N], int n, int* setIndex, int count[], int taille_solution) {
    int i,j;
    for (i = 0; i < *setIndex; i++) {
        int trouve = 1;
        for (j = 0; j < taille_solution; j++) {
            if (solutionSet[i][j] != count[j]) {
                trouve = 0;
                break;
            }
        }
        if (trouve) {
            return 1;
        }
    }
    return 0;
}
void afficherSolutions(int W, int poids[], int valeur[], int K[], int n, int count[], int solutionSet[][N], int* setIndex) {
    if (W == 0) {
        if (existence_solution(solutionSet, n, setIndex, count, n)) {
            return;
        }
        for (int i = 0; i < n; i++) {
            solutionSet[*setIndex][i] = count[i];
        }
        (*setIndex)++;


        printf("{");
        for (int i = 0; i < n; i++) {
            printf("%d", count[i]);
            if (i != n - 1) {
                printf(",");
            }
        }
        printf("}\n");
    } else {
        for (int i = 0; i < n; i++) {
            if (poids[i] <= W && K[W] == valeur[i] + K[W - poids[i]]) {
                count[i]++;
                afficherSolutions(W - poids[i], poids, valeur, K, n, count, solutionSet, setIndex);
                count[i]--;
            }
        }
    }
}

int sacADos(int poids_sac, int poids[], int valeur[], int n, int count[]) {
    int i, weight;
    int K[poids_sac + 1];

    K[0] = 0;

    for (weight = 1; weight <= poids_sac; weight++) {
        K[weight] = 0;
        for (i = 0; i < n; i++) {
            if (poids[i] <= weight) {
                K[weight] = maximum(K[weight], valeur[i] + K[weight - poids[i]]);
            }
        }
    }

    int solutionSet[N][N];
    int setIndex = 0;

    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];
}


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;
}