إخلاء المسؤولية: الطريقة الموضحة أدناه ليست عالمية ، لكنها غالبًا ما تحل مشكلة أو تساعدك في الوصول إلى الحل الصحيح.
إذا كانت هناك مجموعة من الفجوات الموجودة على بعض المحاور (عادةً ما يكون محور الوقت أو مؤشرات بعض المصفوفات) وتحتاج إلى اختيار بعضها بالطريقة المثلى حتى لا تتقاطع الفجوات المحددة ، فعليك محاولة استخدام البرمجة الديناميكية .
مخطط الحل التقريبي:
في البداية ، نقوم بفرز الفجوات المتاحة بالحد الصحيح. لنبدأ الديناميكيات التالية: dp [i] - إجابة الفواصل الزمنية الأولى. & nbsp؛
سنعيد الحساب على النحو التالي: أولاً ، ضع في اعتبارك الموقف الذي لن يتم فيه استخدام هذا الفاصل الزمني ، ثم فقط dp [i] = dp [i-1]. لاحظ أن هذا يضمن أن قيم dp [i] لا تنقص مع نمو i. وهذا منطقي لأن. بإضافة فجوة جديدة ، لا يمكننا تفاقم الإجابة العالمية: إما أننا ببساطة نتجاهل الفجوة الجديدة ، أو نقوم ببناء متغير أكثر ربحية باستخدامه. الآن ، إذا أردنا استخدام الفجوة i ، فيمكننا استخدام تلك الفجوات التي تكون حدودها اليمنى أقل من الحد الأيسر للفجوة الحالية ، حيث يتعين علينا اختيار مجموعة من الفجوات غير المتداخلة. للقيام بذلك ، قمنا في البداية بفرز الفجوات حسب الحد الأيمن ، حتى نتمكن الآن من إيجاد الموضع المطلوب بكفاءة. يمكن القيام بذلك بشكل تحليلي ، إن أمكن ، ولكن في الحالة العامة ، من الممكن العثور على فجوة باستخدام binsearch ، يكون الحد الأيمن منها أقل من الحد الأيسر للحد الحالي ، وفي نفس الوقت ، الحد الأقصى الممكن واحد. نريد تعظيم الحدود الصحيحة لأسباب جشعة ، لأن كلما كبرت ، يمكن أن تزيد الإجابة فقط. وفقًا لذلك ، نجد الموضع المطلوب p ونعيد حساب dp [i] خلال dp [p] والفاصل i.