حقيبة العناصر الكسرية حسب النسبة
اختيار الأعلى قيمةً لكل وحدة وزن أولًا
حقيبة العناصر الكسرية حسب النسبة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
إعداد مسألة حقيبة الظهر
لديك عناصر لكل منها قيمة ووزن، وحقيبة ذات سعة محدودة. والهدف هو حمل أكبر قيمة إجمالية ممكنة. 🎒
النسخة الكسرية تعني إمكانية التقسيم
في النسخة الكسرية، يمكنك أخذ جزء من العنصر، مثل نصف كيس من الحبوب. وهذه الحرية هي ما يتيح للأسلوب الجشع أن ينجح هنا.
القيمة لكل وحدة وزن
المقياس الأساسي هو نسبة قيمة كل عنصر إلى وزنه. وتعني النسبة العالية احتواء مساحة صغيرة جدًا على قيمة كبيرة.
ratio = value / weightالفرز حسب أفضل نسبة
رتّب العناصر حسب القيمة لكل وحدة وزن، بدءًا من الأعلى. وتتمثل الخطة الجشعة في الاستمرار بأخذ أعلى قيمة متاحة بالنسبة إلى المساحة.
items.sort(key=lambda i: i[0] / i[1], reverse=True)خذ العنصر كاملًا ما دام يتسع
مرّ على القائمة المرتبة وخذ كل عنصر بالكامل إذا كان لا يزال يتسع في السعة المتبقية. ثم أضف قيمته الكاملة إلى مجموعك.
if weight <= cap:
total += value
cap -= weightاملأ الفجوة الأخيرة
عندما يكون العنصر أكبر من المساحة المتبقية، خذ جزءًا منه يملأ المساحة المتبقية تمامًا. عندها تمتلئ الحقيبة وتتوقف.
total += value * (cap / weight)لماذا ينجح ترتيب النسبة
ينبغي أن تحتوي كل وحدة من السعة على أكبر قيمة ممكنة، لذلك يجب أن يأتي العنصر الأعلى كثافة أولًا. أما استبداله بعنصر أقل كثافة فلا يؤدي إلا إلى خسارة القيمة.
حقيبة الظهر 0/1 مختلفة
إذا كانت العناصر لا يمكن تقسيمها، تفشل الخوارزمية الجشعة المعتمدة على النسبة. يتطلب الإصدار 0/1 استخدام البرمجة الديناميكية، وليس هذا الفرز البسيط.
زمن التنفيذ
يكلف الفرز حسب النسبة O(n log n)، بينما تكون حلقة الملء خطية. وهذا سريع بما يكفي لحدود مسابقات البرمجة المعتادة.
انتبه إلى الكسر الأخير
استخدم أعدادًا بفاصلة عائمة أو أعدادًا نسبية دقيقة للعنصر الجزئي. قد يؤدي التقريب إلى عدد صحيح مبكرًا إلى إنقاص القيمة والتسبب في إجابة خاطئة.
أين تظهر هذه الفكرة
فكّر في تحميل البضائع، أو مزج الوقود، أو تقسيم الموارد. كلما أمكن تقسيم الأجزاء، كانت الخوارزمية الجشعة المعتمدة على النسبة هي أداتك.
فحص سريع
أنت تملأ حقيبة في مسألة حقيبة الظهر الكسرية.
مراجعة
رتّب العناصر حسب القيمة لكل وحدة وزن، وخذ العناصر الكاملة ما دامت تتسع، ثم خذ كسرًا لإكمال الحقيبة. تكون هذه الخوارزمية الجشعة مثالية فقط عندما يمكن تقسيم العناصر. 🚀
الأسئلة الشائعة
هل درس «حقيبة العناصر الكسرية حسب النسبة» مجاني؟
نعم — نص درس «حقيبة العناصر الكسرية حسب النسبة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «حقيبة العناصر الكسرية حسب النسبة»؟
اختيار الأعلى قيمةً لكل وحدة وزن أولًا تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «حقيبة العناصر الكسرية حسب النسبة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- العقلية الجشعة
- اختيار الأنشطة حسب أقرب وقت انتهاء
- حقيبة العناصر الكسرية حسب النسبة
- اكتشاف فشل النهج الجشع