Sac à dos optimisé en espace
Réduire une structure 2D à une seule ligne
Sac à dos optimisé en espace est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Pourquoi optimiser l'espace
Une table complète utilise n fois cap cases en mémoire, ce qui peut devenir énorme pour de grandes entrées. L'optimisation de l'espace réduit ce coût à une seule ligne réutilisée.
Seule la dernière ligne compte
Remarquez que chaque case ne lit que la ligne précédente, jamais une ligne plus ancienne. Vous n'avez donc jamais besoin de conserver toute la grille en même temps.
Réduisez à un seul tableau
Conservez un seul tableau dp de longueur cap+1. En traitant chaque objet, vous le réécrivez sur place pour représenter la nouvelle ligne.
dp = [0] * (cap + 1)Le piège de la réutilisation
Si vous parcourez la capacité de gauche à droite, dp[w - wt[i]] peut déjà avoir été mis à jour pour ce même objet. Vous pourriez alors prendre l'objet i deux fois.
Parcourez la capacité en sens inverse
La solution consiste à parcourir la capacité de la plus grande valeur à la plus petite. Le parcours en sens inverse garantit que dp[w - wt[i]] contient encore la valeur de l'objet précédent.
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Pourquoi le parcours inverse fonctionne
Lorsque vous calculez dp[w], l'indice plus petit w - wt[i] est encore intact pour ce tour ; il représente donc bien la ligne précédente.
Arrêtez-vous au poids
Les capacités inférieures à wt[i] ne peuvent pas accueillir l'objet, la boucle s'arrête donc à wt[i]. Les ignorer économise quelques itérations sans conséquence.
La boucle complète
La solution entière tient dans deux boucles imbriquées sur un seul tableau. Les objets à l'extérieur, la capacité en sens inverse à l'intérieur, et la réponse apparaît naturellement.
for i in range(n):
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Lisez la dernière case
Après tous les objets, dp[cap] contient la valeur maximale. C'est le même nombre que fournirait la table 2D, avec beaucoup moins de mémoire.
Même durée, moins de mémoire
Vous n'avez pas accéléré l'algorithme : il nécessite toujours un travail de l'ordre de n fois cap. Vous avez seulement réduit la mémoire d'un coût quadratique à un coût linéaire.
Quand cette méthode est utile
Cette astuce vous sauve lorsque cap est grand et que la grille 2D dépasserait la limite de mémoire. C'est un grand classique de la programmation compétitive qu'il vaut la peine de mémoriser.
Vérification rapide
Vérifiez la règle essentielle du sac à dos 1D.
Récapitulatif
Vous avez réduit la table 2D à un seul tableau et parcouru la capacité en sens inverse pour rester correct, en échangeant une mémoire quadratique contre une mémoire linéaire. 🚀
Questions Fréquemment Posées
La leçon « Sac à dos optimisé en espace » est-elle gratuite ?
Oui — le texte complet de « Sac à dos optimisé en espace » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Sac à dos optimisé en espace » ?
Réduire une structure 2D à une seule ligne Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Sac à dos optimisé en espace » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Sac à dos 0/1 : prendre ou laisser
- Sac à dos optimisé en espace
- DP non bornée et rendu de monnaie
- Somme de sous-ensemble et partition