Le problème du sac à dos 0/1 est un défi classique en programmation dynamique où il s'agit de sélectionner un sous-ensemble d'objets, chacun ayant un poids et une valeur, pour les placer dans un sac à dos de capacité limitée. La particularité "0/1" indique que chaque objet ne peut être pris qu'une seule fois ou pas du tout. Cet article se concentre sur le dénombrement des solutions pour deux variations de ce problème : compter les façons d'attteindre une capacité exacte et compter les façons d'obtenir la valeur maximale.

1. Dénombrement des façons de remplir exactement une capacité cible

Considérons un ensemble de \(N\) objets. Chaque objet \(i\) est caractérisé par un poids \(p_i\). Nous disposons d'un sac à dos dont la capacité maximale est \(C\). L'objectif est de déterminer le nombre total de sous-ensembles d'objets dont la somme des poids est exactement égale à \(C\).

Nous abordons ce problème en utilisant une approche de programmation dynamique. Définissons un tableau unidimensionnel nommé compte\_poids\_total où compte\_poids\_total\[c\] représente le nombre de manières distinctes d'atteindre un poids cumulé de \(c\) en utilisant les objets disponibles.

• Initialisation : compte\_poids\_total\[0\] = 1. Ceci signifie qu'il y a une unique façon d'obtenir un poids total de 0 : en ne choisissant aucun objet. Toutes les autres entrées du tableau, pour \(c > 0\), sont initialisées à 0.
• Transition : Pour chaque objet \(i\) (allant de 0 à \(N-1\)) avec son poids \(p_i\), nous itérons sur les capacités \(c\) en partant de la capacité maximale \(C\) et en descendant jusqu'à \(p_i\). Si l'on peut inclure l'objet \(i\) sans dépasser la capacité \(c\), nous ajoutons le nombre de façons d'atteindre la capacité \(c - p_i\) (sans l'objet courant) au nombre de façons d'atteindre la capacité \(c\). La formule de transition est la suivante : \[ \text{compte\_poids\_total}[c] \leftarrow \text{compte\_poids\_total}[c] + \text{compte\_poids\_total}[c - p_i] \] L'itération des capacités de \(C\) vers \(p_i\) est cruciale pour garantir que chaque objet n'est pris en compte qu'une seule fois dans la construction d'un sous-ensemble (ce comportement est caractéristique du sac à dos 0/1).

Une fois tous les objets traités, la valeur stockée dans compte\_poids\_total\[C\] sera le nombre de façons d'atteindre exactement la capacité \(C\).

#include <iostream>
#include <vector>
#include <numeric> // Non utilisé ici, mais parfois utile pour initialisations

// Utilisation de 'long long' pour gérer de grands nombres de combinaisons
using ll = long long;

void resoudre_compte_capacite_exacte() {
    int nbr_objets = 0;
    ll capacite_max = 0;
    std::cin >> nbr_objets >> capacite_max;

    std::vector<ll> poids_objets(nbr_objets);
    // Les valeurs des objets ne sont pas nécessaires pour ce sous-problème
    for (int i = 0; i < nbr_objets; ++i) {
        std::cin >> poids_objets[i];
    }

    // compte_poids_total[c] : nombre de façons d'atteindre un poids cumulé 'c'
    std::vector<ll> compte_poids_total(capacite_max + 1, 0);
    compte_poids_total[0] = 1; // Une seule façon d'obtenir un poids de 0 (ne rien prendre)

    // Itérer sur chaque objet disponible
    for (int i = 0; i < nbr_objets; ++i) {
        ll poids_courant_objet = poids_objets[i];
        // Itérer sur les capacités de manière décroissante pour un traitement 0/1
        for (ll c = capacite_max; c >= poids_courant_objet; --c) {
            compte_poids_total[c] += compte_poids_total[c - poids_courant_objet];
        }
    }

    std::cout << compte_poids_total[capacite_max] << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    // int nombre_de_tests = 1;
    // std::cin >> nombre_de_tests; // Décommenter pour plusieurs cas de test
    // while (nombre_de_tests--) {
        resoudre_compte_capacite_exacte();
    // }
    return 0;
}
</ll></ll></numeric></vector></iostream>

2. Dénombrement des façons d'attteindre la valeur maximale globale

Cette deuxième variation du problème du sac à dos 0/1 requiert deux étapes : d'abord identifier la valeur maximale qu'il est possible d'obtenir en remplissant le sac à dos jusqu'à sa capacité \(C\), puis compter le nombre de combinaisons d'objets distinctes qui permettent d'atteindre précisément cette valeur maximale.

Pour ce faire, nous utiliserons deux tableaux de programmation dynamique :

• valeur\_optimale\[c\] : Représente la valeur maximale que l'on peut obtenir avec une capacité totale de \(c\).
• nb\_manieres\_opt\[c\] : Représente le nombre de façons d'atteindre cette valeur\_optimale\[c\] pour la capacité \(c\).

Initialisation :

• valeur\_optimale\[0\] = 0. La valeur maximale pour une capacité de 0 est 0. Pour toutes les autres capacités \(c > 0\), valeur\_optimale\[c\] est initialisée à une valeur très petite (par exemple, std::numeric\_limits<ll>::min()) pour indiquer qu'aucune solution n'a encore été trouvée pour ces capacités.
• nb\_manieres\_opt\[0\] = 1. Il y a une manière d'obtenir une valeur de 0 avec une capacité de 0 (en ne prenant aucun objet). Toutes les autres entrées de nb\_manieres\_opt\[c\] sont initialisées à 0.

Transitions :

Pour chaque objet \(i\) (allant de 0 à \(N-1\)) avec son poids \(p_i\) et sa valeur \(v_i\), nous itérons sur les capacités \(c\) de \(C\) à \(p_i\). Pour chaque capacité \(c\), nous évaluons l'impact de l'inclusion de l'objet \(i\) :

1. Calculer la valeur potentielle si l'objet \(i\) est inclus : val\_avec\_obj = valeur\_optimale\[c - p\_i\] + v\_i. Il faut s'assurer que valeur\_optimale\[c - p\_i\] n'était pas l'état "inatteignable" (std::numeric\_limits<ll>::min()).
2. Comparer val\_avec\_obj avec valeur\_optimale\[c\] (qui représente la meilleure valeur pour la capacité \(c\) sans l'objet \(i\), ou déjà optimisée par des objets précédents) :

• **Si val\_avec\_obj > valeur\_optimale\[c\] :**L'inclusion de l'objet \(i\) conduit à une valeur strictement meilleure. Nous mettons à jour valeur\_optimale\[c\] = val\_avec\_obj et nb\_manieres\_opt\[c\] = nb\_manieres\_opt\[c - p\_i\].
• **Si val\_avec\_obj == valeur\_optimale\[c\] :**L'inclusion de l'objet \(i\) mène à la même valeur optimale. Nous ajoutons le nombre de solutions de ce nouveau chemin aux solutions existantes : nb\_manieres\_opt\[c\] += nb\_manieres\_opt\[c - p\_i\].
• **Si val\_avec\_obj < valeur\_optimale\[c\] :**Ne rien faire, la meilleure solution actuelle pour la capacité \(c\) est supérieure ou égale à celle obtenue en incluant l'objet \(i\).

Détermination du résultat final :

Après avoir traité tous les objets et mis à jour les tableaux DP, nous devons trouver la valeur maximale globale max\_valeur\_globale parmi toutes les valeur\_optimale\[c\] pour \(c\) allant de 0 à \(C\). Enfin, nous additionnons toutes les nb\_manieres\_opt\[c\] correspondant aux capacités \(c\) pour lesquelles valeur\_optimale\[c\] est égale à cette max\_valeur\_globale.

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::max
#include <limits>    // Pour std::numeric_limits

using ll = long long;

void resoudre_compte_optimal_valeur() {
    int nbr_objets = 0;
    ll capacite_max = 0;
    std::cin >> nbr_objets >> capacite_max;

    std::vector<ll> poids_objets(nbr_objets);
    std::vector<ll> valeurs_objets(nbr_objets);

    for (int i = 0; i < nbr_objets; ++i) {
        std::cin >> poids_objets[i] >> valeurs_objets[i];
    }

    // valeur_optimale[c]: valeur max atteignable pour la capacité 'c'
    // nb_manieres_opt[c]: nombre de façons d'atteindre valeur_optimale[c]
    std::vector<ll> valeur_optimale(capacite_max + 1, std::numeric_limits<ll>::min());
    std::vector<ll> nb_manieres_opt(capacite_max + 1, 0);

    valeur_optimale[0] = 0; // Valeur 0 pour capacité 0
    nb_manieres_opt[0] = 1; // Une façon d'obtenir 0 valeur avec 0 capacité

    for (int i = 0; i < nbr_objets; ++i) {
        ll poids_courant = poids_objets[i];
        ll valeur_courante = valeurs_objets[i];

        for (ll c = capacite_max; c >= poids_courant; --c) {
            // Calculer la valeur si l'objet courant est pris
            ll val_si_pris;
            if (valeur_optimale[c - poids_courant] == std::numeric_limits<ll>::min()) {
                // Si la capacité précédente (c - poids_courant) n'était pas atteignable
                val_si_pris = std::numeric_limits<ll>::min();
            } else {
                val_si_pris = valeur_optimale[c - poids_courant] + valeur_courante;
            }

            // Comparer avec la valeur actuellement optimale pour la capacité 'c'
            if (val_si_pris > valeur_optimale[c]) {
                // L'objet courant offre une valeur strictement meilleure
                valeur_optimale[c] = val_si_pris;
                nb_manieres_opt[c] = nb_manieres_opt[c - poids_courant];
            } else if (val_si_pris == valeur_optimale[c]) {
                // L'objet courant offre la même valeur optimale, ajouter les façons
                nb_manieres_opt[c] += nb_manieres_opt[c - poids_courant];
            }
            // Si val_si_pris < valeur_optimale[c], ne rien faire (solution actuelle est meilleure)
        }
    }

    // Trouver la valeur maximale possible sur toutes les capacités
    ll valeur_optimale_globale = 0;
    for (ll c = 0; c <= capacite_max; ++c) {
        if (valeur_optimale[c] != std::numeric_limits<ll>::min()) { // Ignorer les capacités inatteignables
            valeur_optimale_globale = std::max(valeur_optimale_globale, valeur_optimale[c]);
        }
    }

    // Compter le nombre total de façons d'atteindre cette valeur maximale globale
    ll total_solutions_optimales = 0;
    for (ll c = 0; c <= capacite_max; ++c) {
        if (valeur_optimale[c] == valeur_optimale_globale) {
            total_solutions_optimales += nb_manieres_opt[c];
        }
    }

    std::cout << total_solutions_optimales << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    // int nombre_de_tests = 1;
    // std::cin >> nombre_de_tests; // Décommenter pour plusieurs cas de test
    // while (nombre_de_tests--) {
        resoudre_compte_optimal_valeur();
    // }
    return 0;
}
</ll></ll></ll></ll></ll></ll></ll></ll></limits></algorithm></vector></iostream>