أقصى ربح
Problem
أنت تعمل كمدير وتضع خطة عمل للشهر القادم. ينقسم كل شهر إلى وحدات زمنية متساوية T . هناك مهام n في المجمل يجب القيام بها. ومع ذلك ، فأنت تدرك أنه قد لا يكون من الممكن إكمال جميع المهام في شهر واحد وتريد وضع خطة مثالية باختيار بعضها لإكمالها.
لكل مهمة ، نعرف الوقت t i الذي يجب إنفاقه لإكمالها ، بالإضافة إلى الربح p i < / sub> التي ستجلبها المهمة المكتملة للشركة. تريد التخطيط لبعض المهام بحيث:
- إجمالي الوقت المستغرق في المهام المدرجة في الخطة لم يتجاوز
T .
- إجمالي الربح من هذه المهام كان الحد الأقصى.
ضع خطة لها الخصائص الموضحة أعلاه وحدد الربح الناتج عن تنفيذ هذه الخطة.
الرجاء ملاحظة أن الخطة الوحيدة التي تطابق الشروط قد لا تحتوي على أية مهام.
على & nbsp؛
إدخال البيانات
يحتوي السطر الأول & nbsp؛ على الأرقام الطبيعية T & nbsp؛ (1 & le؛ T & le؛ 100 & thinsp؛ 000) و n & nbsp؛ (1 & le؛ n & le ؛ 10) - - عدد الوحدات الزمنية في الشهر وعدد المهام.
تحتوي السطور التالية n & nbsp؛ على رقمين طبيعيين كل منهما t i و p i & nbsp؛ (1 & lt؛ = & nbsp؛ t i ، p i & nbsp؛ & lt؛ = & nbsp؛ 100 & thinsp؛ 000) - & nbsp؛ الوقت الذي تقضيه في أكمل مهمة i والربح الذي يمكن تحقيقه بإكمالها.
بيانات الدمغة
طباعة رقم واحد & nbsp؛ & mdash؛ أقصى ربح يمكن الحصول عليه من خلال وضع خطة تفي بالشروط المذكورة أعلاه.
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
10 3
8100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |