حقيبة العناصر الكسرية حسب النسبة

لديك عناصر لكل منها قيمة ووزن، وحقيبة ذات سعة محدودة. والهدف هو حمل أكبر قيمة إجمالية ممكنة. 🎒

في النسخة الكسرية، يمكنك أخذ جزء من العنصر، مثل نصف كيس من الحبوب. وهذه الحرية هي ما يتيح للأسلوب الجشع أن ينجح هنا.

المقياس الأساسي هو نسبة قيمة كل عنصر إلى وزنه. وتعني النسبة العالية احتواء مساحة صغيرة جدًا على قيمة كبيرة.

رتّب العناصر حسب القيمة لكل وحدة وزن، بدءًا من الأعلى. وتتمثل الخطة الجشعة في الاستمرار بأخذ أعلى قيمة متاحة بالنسبة إلى المساحة.

مرّ على القائمة المرتبة وخذ كل عنصر بالكامل إذا كان لا يزال يتسع في السعة المتبقية. ثم أضف قيمته الكاملة إلى مجموعك.

عندما يكون العنصر أكبر من المساحة المتبقية، خذ جزءًا منه يملأ المساحة المتبقية تمامًا. عندها تمتلئ الحقيبة وتتوقف.

ينبغي أن تحتوي كل وحدة من السعة على أكبر قيمة ممكنة، لذلك يجب أن يأتي العنصر الأعلى كثافة أولًا. أما استبداله بعنصر أقل كثافة فلا يؤدي إلا إلى خسارة القيمة.

إذا كانت العناصر لا يمكن تقسيمها، تفشل الخوارزمية الجشعة المعتمدة على النسبة. يتطلب الإصدار 0/1 استخدام البرمجة الديناميكية، وليس هذا الفرز البسيط.

يكلف الفرز حسب النسبة O(n log n)، بينما تكون حلقة الملء خطية. وهذا سريع بما يكفي لحدود مسابقات البرمجة المعتادة.

استخدم أعدادًا بفاصلة عائمة أو أعدادًا نسبية دقيقة للعنصر الجزئي. قد يؤدي التقريب إلى عدد صحيح مبكرًا إلى إنقاص القيمة والتسبب في إجابة خاطئة.

فكّر في تحميل البضائع، أو مزج الوقود، أو تقسيم الموارد. كلما أمكن تقسيم الأجزاء، كانت الخوارزمية الجشعة المعتمدة على النسبة هي أداتك.

رتّب العناصر حسب القيمة لكل وحدة وزن، وخذ العناصر الكاملة ما دامت تتسع، ثم خذ كسرًا لإكمال الحقيبة. تكون هذه الخوارزمية الجشعة مثالية فقط عندما يمكن تقسيم العناصر. 🚀