حقيبة 0/1: خذ أو اترك
تعظيم القيمة ضمن حدّ للوزن
حقيبة 0/1: خذ أو اترك درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 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) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «حقيبة 0/1: خذ أو اترك»؟
تعظيم القيمة ضمن حدّ للوزن تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «حقيبة 0/1: خذ أو اترك»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- حقيبة 0/1: خذ أو اترك
- حقيبة محسّنة من حيث المساحة
- برمجة ديناميكية للحقيبة غير المحدودة وتبديل العملات
- مجموع المجموعة والتقسيم