حقيبة 0/1: خذ أو اترك
تعظيم القيمة ضمن حدّ للوزن
حقيبة 0/1: خذ أو اترك درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
قصة حقيبة الظهر
لديك حقيبة ذات حد للوزن وكومة من العناصر. تسأل مسألة 0/1 knapsack: ما العناصر التي تعظّم القيمة من دون تجاوز سعة الحقيبة؟ 🎒
خذ أو اترك
تعني عبارة 0/1 أن كل عنصر يُؤخذ كاملًا أو يُترك كاملًا. لا يمكنك أخذ نصف عنصر، لذا يكون كل اختيار نعم أو لا.
لماذا يفشل الجشع
قد يؤدي أخذ العنصر الأرخص أو الأعلى قيمة أولًا إلى إهدار السعة. تفشل هنا حيلة الاختيار الجشع، لذا عليك دراسة التوليفات الفعلية.
المدخلان
تُعطى قائمتان متوازيتان: وزن وقيمة لكل عنصر، إضافة إلى سعة واحدة. للعنصر i الوزن wt[i] والقيمة val[i].
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7عرّف الحالة
لتكن dp[i][w] أفضل قيمة باستخدام أول i من العناصر وبسعة w. إن تسمية الحالة بدقة هي جوهر المسألة.
خيار التخطي
إذا تخطيت العنصر i، فقيمتك هي ما كان لديك مسبقًا: dp[i-1][w]. وتبقى السعة كما هي لبقية العناصر.
خيار الأخذ
إذا أخذت العنصر i، فأضف قيمته وقلّل السعة: val[i] + dp[i-1][w - wt[i]]. ولا يكون ذلك ممكنًا إلا عندما تكون w أكبر من wt[i] أو مساوية لها.
اختر الفرع الأفضل
تحتفظ العلاقة التكرارية ببساطة بالخيار الأكبر باستخدام max. تعتمد كل خلية على الإجابات المحسوبة مسبقًا في الصف السابق.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])صف الأساس
مع عدم وجود أي عناصر، يمكنك حمل قيمة صفر عند أي سعة. تملأ حالة الأساس هذه الصف الأول كله بالأصفار لتبني عليه.
dp = [[0] * (cap + 1) for _ in range(n + 1)]املأ الجدول
كرّر على العناصر في الحلقة الخارجية، وعلى السعات في الحلقة الداخلية. تقرأ كل خلية الصف السابق فقط، لذا تملأ عملية مرور واحدة الجدول بأكمله.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]اقرأ الإجابة
تحتوي الخلية السفلية اليمنى dp[n][cap] على القيمة القصوى لجميع العناصر ومع كامل السعة. وهذه الخلية الواحدة هي إجابتك النهائية.
تحقق سريع
اختبر العلاقة التكرارية الأساسية لمسألة 0/1 knapsack.
مراجعة
تعلّمت مسألة 0/1 knapsack: كل عنصر إما أن يؤخذ أو يُترك، وتحتفظ dp[i][w] بالأفضل بين التخطي والأخذ، وتكون dp[n][cap] هي الإجابة. 🎉
الأسئلة الشائعة
هل درس «حقيبة 0/1: خذ أو اترك» مجاني؟
نعم — نص درس «حقيبة 0/1: خذ أو اترك» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «حقيبة 0/1: خذ أو اترك»؟
تعظيم القيمة ضمن حدّ للوزن تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «حقيبة 0/1: خذ أو اترك»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- حقيبة 0/1: خذ أو اترك
- حقيبة محسّنة من حيث المساحة
- برمجة ديناميكية للحقيبة غير المحدودة وتبديل العملات
- مجموع المجموعة والتقسيم