La programmation dynamique est une technique puissante pour résoudre une vaste gamme de problèmes. Parmi eux, les problèmes de sac à dos sont des classiques qui se déclinent en plusieurs variantes. Cette section explore l'application des modèles de sac à dos 0/1 (où chaque article peut être utilisé au plus une fois) et illimité (où chaque article peut être utilisé pluseiurs fois) pour des problèmes de comptage de combinaisons.

1. Combinaisons de Nombres

---

Problème : Étant donné N entiers positifs A₁, A₂, ..., Aₙ, sélectionnez un sous-ensemble de ces nombres dont la somme est égale à M. Déterminez le nombre total de façons de former cette somme.

Format d'entrée :

• La première ligne contient deux entiers, N et M.
• La deuxième ligne contient N entiers représentant A₁, A₂, ..., Aₙ.

Format de sortie :

• Un unique entier, le nombre de schémas de sélection possibles.

Contraintes :

• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 10000
• 1 ≤ Aᵢ ≤ 1000
• La réponse est garantie de tenir dans un entier 32 bits.

Exemple d'entrée :

4 4
1 1 2 2

Exemple de sortie :

3

Approche par Programmation Dynamique (Modèle Sac à Dos 0/1) :

Ce problème est une application directe du modèle du sac à dos 0/1, où l'on cherche à compter le nombre de façons d'atteindre une somme cible, plutôt que de maximiser une valeur. L'état dp[s] représente le nombre de sous-ensembles des nombres déjà traités dont la somme est s. Lorsque nous considérons un nouvel élément val, nous mettons à jour les états : pour chaque somme s possible, le nombre de façons d'atteindre s est la somme des façons d'atteindre s sans utiliser val et des façons d'atteindre s - val puis d'ajouter val.

Pour une optimisation de l'espace en utilisant un tableau 1D (dp[s]), il est crucial que la boucle interne itérant sur les sommes s aille du maximum (la somme cible) vers 0. Cela garantit que chaque nombre est utilisé au plus une fois pour former une somme donnée au cours de l'itération actuelle sur les éléments.

L'équation de transition d'état (implicite dans la boucle 1D) est : dp[s] = dp[s] + dp[s - val].

Implémentation en C++ :

#include <iostream>
#include <vector>
#include <numeric> // Pour std::iota ou autres si nécessaire
#include <algorithm> // Pour std::sort si nécessaire

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int nombreElements, sommeCible;
    std::cin >> nombreElements >> sommeCible;

    std::vector<int> valeursElements(nombreElements);
    for (int i = 0; i < nombreElements; ++i) {
        std::cin >> valeursElements[i];
    }

    // dp[s] représente le nombre de façons d'obtenir la somme 's'.
    // Nous utilisons une optimisation en espace avec un vecteur 1D.
    std::vector<int> dp(sommeCible + 1, 0);
    dp[0] = 1; // Il y a une façon de former la somme 0 (en ne choisissant aucun élément).

    // Pour chaque élément disponible
    for (int valeurActuelle : valeursElements) {
        // Itérer sur les sommes possibles, de la sommeCible jusqu'à la valeurActuelle.
        // Cette direction descendante garantit que chaque valeurActuelle est utilisée
        // au plus une fois pour former une somme 's' (modèle 0/1).
        for (int s = sommeCible; s >= valeurActuelle; --s) {
            dp[s] += dp[s - valeurActuelle];
        }
    }

    std::cout << dp[sommeCible] << std::endl;

    return 0;
}

2. Achat de Livres

---

Problème : Vous disposez de N unités monétaires pour acheter des livres. Les livres sont disponibles à des prix de 10, 20, 50 et 100 unités. Chaque type de livre peut être acheté en plusieurs exemplaires. Combien de façons différentes existe-t-il de dépenser la totalité de votre argent ?

Format d'entrée :

• Un entier unique N, représentant le montant total d'argent.

Format de sortie :

• Un entier unique, le nombre de combinaisons d'achat.

Contraintes :

• 0 ≤ N ≤ 1000

Exemples d'entrée/sortie :

Entrée 1: 20 -> Sortie 1: 2
Entrée 2: 15 -> Sortie 2: 0
Entrée 3: 0  -> Sortie 3: 1

Approche par Programmation Dynamique (Modèle Sac à Dos Illimité) :

Puisque chaque type de livre peut être acheté plusieurs fois, ce scénario correspond au modèle du sac à dos illimité. L'objectif est encore de compter les combinaisons. L'état dp[montant] représente le nombre de façons d'atteindre un certain montant avec les prix de livres considérés jusqu'à présent.

Pour l'optimisation en espace avec un tableau 1D, la boucle interne itérant sur les montant doit aller de 0 jusqu'à la capacité maximale. Cela permet de réutiliser les articles du type actuel pour former des sommes plus grandes dans la même itération. L'équation de transition est : dp[montant] = dp[montant] + dp[montant - prixActuel].

Implémentation en C++ :

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int argentTotal;
    std::cin >> argentTotal;

    std::vector<int> prixLivres = {10, 20, 50, 100};

    // dp[montant] stocke le nombre de façons de dépenser 'montant'
    std::vector<long long> dp(argentTotal + 1, 0);
    dp[0] = 1; // Il y a une façon de dépenser 0 (ne rien acheter).

    // Pour chaque type de livre disponible
    for (int prixActuel : prixLivres) {
        // Itérer sur les montants possibles, du prix actuel jusqu'à l'argentTotal.
        // Cette direction ascendante permet de réutiliser le livre actuel
        // pour former des montants (modèle sac à dos illimité).
        for (int montant = prixActuel; montant <= argentTotal; ++montant) {
            dp[montant] += dp[montant - prixActuel];
        }
    }

    std::cout << dp[argentTotal] << std::endl;

    return 0;
}

3. Système Monétaire 1

---

Problème : Un système monétaire dispose de N dénominations différentes. Déterminez le nombre de façons de former une somme M en utilisant ces dénominations, sachant que chaque dénomination est disponible en quantité illimitée.

Format d'entrée :

• La première ligne contient deux entiers N et M.
• Les N lignes suivantes conteinnent chacune un entier, représentant une dénomination.

Format de sortie :

• Une ligne contenant un entier unique, le nombre de façons.

Contraintes :

• N ≤ 15
• M ≤ 3000

Approche par Programmation Dynamique (Modèle Sac à Dos Illimité) :

C'est une généralisation directe du problème d'achat de livres. Le même modèle de sac à dos illimité s'applique. Nous cherchons le nombre de façons d'atteindre une somme cible avec un ensemble de dénominations, chacune disponible à l'infini. L'état dp[somme] représente le nombre de façons de former somme. La transition reste dp[somme] += dp[somme - valeurMonnaie], avec la boucle interne allant du bas vers le haut.

Implémentation en C++ :

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int nombreDenominations, montantCible;
    std::cin >> nombreDenominations >> montantCible;

    std::vector<int> denominations(nombreDenominations);
    for (int i = 0; i < nombreDenominations; ++i) {
        std::cin >> denominations[i];
    }

    // dp[montant] : nombre de façons de former le 'montant' spécifié
    std::vector<long long> dp(montantCible + 1, 0);
    dp[0] = 1; // Une façon de faire 0 (ne pas utiliser de monnaie).

    // Pour chaque type de monnaie
    for (int valeurMonnaie : denominations) {
        // Mettre à jour les possibilités pour tous les montants à partir de la valeur de la monnaie actuelle.
        // La boucle ascendante permet de réutiliser les monnaies (sac à dos illimité).
        for (int montant = valeurMonnaie; montant <= montantCible; ++montant) {
            dp[montant] += dp[montant - valeurMonnaie];
        }
    }

    std::cout << dp[montantCible] << std::endl;

    return 0;
}

4. Système Monétaire 2

---

Problème : Un pays dispose d'un système monétaire (N, a) avec N dénominations a[1...N]. Chaque monnaie est disponible en quantité illimitée. Deux systèmes monétaires (N, a) et (M, b) sont équivalents si tout montant X qui peut être représenté par l'un peut l'être par l'autre, et vice-versa. Votre tâche est de trouver un système monétaire (M, b) équivalent au système original (N, a), avec M le plus petit possible.

Format d'entrée :

• La première ligne contient un entier T, le nombre de jeux de données.
• Chaque jeu de données commence par un entier positif N.
• La ligne suivante contient N entiers positifs séparés par des espaces, a[1...N].

Format de sortie :

• Pour chaque jeu de données, une ligne contenant un entier positif unique, le M minimal.

Contraintes :

• 1 ≤ N ≤ 100
• 1 ≤ a[i] ≤ 25000
• 1 ≤ T ≤ 20

Approche par Programmation Dynamique (Détection de Redondance) :

L'objectif est de trouver le plus petit sous-ensemble de dénominations qui peut représenter toutes les sommes que le système original peut représenter. Une dénomination a[i] est redondante si elle peut être formée en utilisant une combinaison des dénominations a[j] où j < i (en supposant que les dénominations sont triées par ordre croissant). Notre approche consiste à trier les dénominations, puis à parcourir la liste. Pour chaque dénomination, nous vérifions si elle peut être formée par les dénominations précédentes. Si c'est le cas, elle est redondante et peut être écartée. Sinon, elle est essentielle et doit être incluse dans notre nouveau système minimal.

Nous utilisons un tableau booléen estAccessible[s] pour indiquer si la somme s peut être formée par les dénominations déjà identifiées comme essentielles. Initialement, estAccessible[0] = true (la somme 0 est toujours réalisable). Pour chaque dénomiantion valeurMonnaie dans l'ordre croissant :

1. Si estAccessible[valeurMonnaie] est vrai, cela signifie que valeurMonnaie peut déjà être formée par des dénominations plus petites et essentielles. Elle est donc redondante. Nous la sautons.
2. Sinon, valeurMonnaie ne peut pas être formée par les dénominations essentielles précédentes. Elle est donc elle-même essentielle. Nous l'ajoutons à notre ensemble minimal (incrémentons notre compteur) et mettons à jour le tableau estAccessible pour toutes les sommes s qui peuvent maintenant être formées en utilisant valeurMonnaie (estAccessible[s] = estAccessible[s] || estAccessible[s - valeurMonnaie]). La mise à jour doit se faire dans l'ordre croissant des sommes pour simuler un sac à dos illimité.

La taille maximale de estAccessible doit correspondre à la plus grande dénomination possible, car toute somme supérieure à la plus grande dénomination peut être formée par une combinaison d'éléments plus petits si elle est représentable, ou elle ne nous intéresse pas pour déterminer la redondance d'une monnaie spécifique (qui est au maximum 25000).

Implémentation en C++ :

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::sort et std::max_element

void resoudreCas() {
    int n;
    std::cin >> n;

    std::vector<int> denominations(n);
    int maxDenomination = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> denominations[i];
        if (denominations[i] > maxDenomination) {
            maxDenomination = denominations[i];
        }
    }

    // Il est crucial de trier les dénominations pour que la logique de redondance fonctionne.
    // Une monnaie ne peut être formée que par des monnaies plus petites (ou égales) déjà traitées.
    std::sort(denominations.begin(), denominations.end());

    // estAccessible[s] est vrai si la somme 's' peut être formée par les dénominations
    // considérées jusqu'à présent (celles qui sont essentielles).
    std::vector<bool> estAccessible(maxDenomination + 1, false);
    estAccessible[0] = true; // La somme 0 est toujours réalisable (en ne prenant rien).

    int comptePiecesEssentielles = 0;

    // Parcourir les dénominations triées
    for (int valeurMonnaie : denominations) {
        // Si cette valeur de monnaie peut déjà être formée par les dénominations essentielles précédentes,
        // alors elle est redondante et n'a pas besoin d'être incluse dans le nouveau système minimal.
        if (estAccessible[valeurMonnaie]) {
            continue;
        }

        // Sinon, cette monnaie est essentielle pour former de nouvelles sommes.
        // L'ajouter à notre ensemble minimal.
        comptePiecesEssentielles++;

        // Avec cette nouvelle monnaie essentielle, mettons à jour toutes les sommes
        // qui peuvent être formées. C'est un processus de sac à dos illimité booléen.
        // La boucle ascendante est nécessaire car 'valeurMonnaie' peut être réutilisée.
        for (int somme = valeurMonnaie; somme <= maxDenomination; ++somme) {
            estAccessible[somme] = estAccessible[somme] || estAccessible[somme - valeurMonnaie];
        }
    }

    std::cout << comptePiecesEssentielles << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        resoudreCas();
    }

    return 0;
}