Sac à dos 0/1 : prendre ou laisser
Maximiser la valeur sous une limite de poids
Sac à dos 0/1 : prendre ou laisser est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 1 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 Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
L'histoire du sac à dos
Vous disposez d'un sac avec une limite de poids et d'un tas d'objets. Le sac à dos 0/1 demande quels objets maximisent la valeur sans dépasser la capacité. 🎒
Prenez ou laissez
Le terme 0/1 signifie que chaque objet est soit entièrement pris, soit entièrement laissé. Vous ne pouvez jamais prendre une partie d'un objet : chaque choix est oui ou non.
Pourquoi l'approche gloutonne échoue
Prendre en premier l'objet le moins cher ou le plus précieux peut gaspiller de la capacité. Le raccourci glouton échoue ici ; vous devez donc examiner les véritables combinaisons.
Les deux entrées
On vous donne deux listes parallèles : un poids et une valeur pour chaque objet, ainsi qu'une capacité. L'objet i a pour poids wt[i] et pour valeur val[i].
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7Définissez l'état
Soit dp[i][w] la meilleure valeur obtenue avec les i premiers objets et une capacité w. Nommer précisément l'état est l'essentiel du problème.
Le choix de laisser l'objet
Si vous laissez l'objet i, votre valeur reste celle que vous aviez déjà : dp[i-1][w]. La capacité reste inchangée pour la suite.
Le choix de prendre l'objet
Si vous prenez l'objet i, ajoutez sa valeur et réduisez la capacité : val[i] + dp[i-1][w - wt[i]]. Cela n'est possible que lorsque w est au moins égal à wt[i].
Choisissez la meilleure branche
La récurrence conserve simplement la plus grande des deux options avec max. Chaque case s'appuie sur les réponses déjà calculées en dessous d'elle.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])La ligne de base
Avec zéro objet, vous pouvez transporter une valeur nulle quelle que soit la capacité. Ce cas de base remplit la première ligne de zéros sur lesquels construire la suite.
dp = [[0] * (cap + 1) for _ in range(n + 1)]Remplissez la table
Parcourez les objets dans la boucle externe et les capacités dans la boucle interne. Chaque case ne lit que la ligne précédente, donc un seul parcours remplit toute la table.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]Lisez la réponse
La case en bas à droite, dp[n][cap], contient la valeur maximale pour tous les objets et la capacité totale. Cette seule case constitue votre réponse finale.
Vérification rapide
Vérifiez la récurrence fondamentale du sac à dos 0/1.
Récapitulatif
Vous avez appris le sac à dos 0/1 : chaque objet est pris ou laissé, dp[i][w] conserve le meilleur choix entre laisser et prendre, et dp[n][cap] est la réponse. 🎉
Questions Fréquemment Posées
La leçon « Sac à dos 0/1 : prendre ou laisser » est-elle gratuite ?
Oui — le texte complet de « Sac à dos 0/1 : prendre ou laisser » 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 Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Sac à dos 0/1 : prendre ou laisser » ?
Maximiser la valeur sous une limite de poids Tu pratiques Competitive Programming Academy 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 Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy 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 1 sur 4.
Combien de temps prend la leçon « Sac à dos 0/1 : prendre ou laisser » ?
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 Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy 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