Le problème du sac à dos complet (ou sans limite) est une variante classique de la programmation dynamique. La différence fondamentale avec le problème du sac à dos 0/1 réside dans le fait que chaque article peut être sélectionné un nombre illimité de fois.

L'équation de transition d'état de base s'écrit :

dp[i][j] = max(dp[i-1][j - k*volume[i]] + k*valeur[i])

pour tout k tel que k*volume[i] <= j.

Approche naïve

Une implémentation directe utilise trois boucles imbriquées pour énumérer toutes les quantités possibles de chaque article. Bien que correcte, cette approche présente une complexité temporelle élevée, ce qui la rend inefficace pour des contraintes de temps strictes.

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

using namespace std;

int main() {
    int numItems, maxCapacity;
    if (!(cin >> numItems >> maxCapacity)) return 0;

    vector<int> volume(numItems + 1), value(numItems + 1);
    for (int i = 1; i <= numItems; ++i) {
        cin >> volume[i] >> value[i];
    }

    vector<vector<int>> dp(numItems + 1, vector<int>(maxCapacity + 1, 0));

    for (int i = 1; i <= numItems; ++i) {
        for (int j = 0; j <= maxCapacity; ++j) {
            for (int k = 0; k * volume[i] <= j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * volume[i]] + k * value[i]);
            }
        }
    }

    cout << dp[numItems][maxCapacity] << "\n";
    return 0;
}

Optimisation de la complexité temporelle

Pour réduire la complexité, analysons la relation de récurrence. En développant les états, on obtient :

dp[i][j] = max(dp[i-1][j], dp[i-1][j - v] + val, dp[i-1][j - 2v] + 2val, ...)
dp[i][j - v] = max(dp[i-1][j - v], dp[i-1][j - 2v] + val, ...)

En comparant ces deux expressions, on peut déduire la relation simplifiée suivante :

dp[i][j] = max(dp[i-1][j], dp[i][j - v] + val)

Cette déduction permet d'éliminer la boucle interne k. Le code bidimensionnel optimisé devient :

for (int i = 1; i <= numItems; ++i) {
    for (int j = 0; j <= maxCapacity; ++j) {
        dp[i][j] = dp[i - 1][j];
        if (j >= volume[i]) {
            dp[i][j] = max(dp[i][j], dp[i][j - volume[i]] + value[i]);
        }
    }
}

Comparaison avec le sac à dos 0/1

En observant attentivement l'équation optimisée, on remarque une similitude frappante avec l'algorithme du sac à dos 0/1. La seule différence réside dans l'indice utilisé pour la capacité restante :

dp[i][j] = max(dp[i][j], dp[i-1][j - volume[i]] + value[i]);  // Sac à dos 0/1
dp[i][j] = max(dp[i][j], dp[i][j - volume[i]] + value[i]);    // Sac à dos complet

Dans le sac à dos complet, l'utilisation de dp[i] au lieu de dp[i-1] permet de réutiliser le même article plusieurs fois.

Optimisation de l'espace mémoire

Puisque l'état actuel ne dépend que de l'état de la ligne actuelle (pour les capacités inférieures) et de la ligne précédente, nous pouvons compresser la matrice 2D en un tableau 1D.

Contrairement au sac à dos 0/1 où la boucle interne est parcourue à l'envers pour éviter la réutilisation d'un article, ici, nous devons parcourir la boucle interne dans l'ordre croissant. Cela garantit que l'article peut être ajouté plusieurs fois.

L'implémentation finale optimisée en temps et en espace est la suivante :

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

using namespace std;

int main() {
    int numItems, maxCapacity;
    if (!(cin >> numItems >> maxCapacity)) return 0;

    vector<int> volume(numItems + 1), value(numItems + 1);
    for (int i = 1; i <= numItems; ++i) {
        cin >> volume[i] >> value[i];
    }

    vector<int> dp(maxCapacity + 1, 0);

    for (int i = 1; i <= numItems; ++i) {
        for (int j = volume[i]; j <= maxCapacity; ++j) {
            dp[j] = max(dp[j], dp[j - volume[i]] + value[i]);
        }
    }

    cout << dp[maxCapacity] << "\n";
    return 0;
}