n الأرقام، N / 2 أزواج.تقليل الحد الأقصى للمبلغ من الاقتران.إثبات الخوارزمية الجشع

Question

لذلك قل لدي أرقام n، حيث n هو حتى. أريد إقران الأرقام بحيث يتم تقليل الحد الأقصى للمبلغ من الأزواج. على سبيل المثال -2، 3، 4، 5. الاقتران المثالي هو (-2، 5)، (3، 4)، نظرا لأن مبلغها الأقصى هو 3 + 4= 7، وهذا هو الحد الأدنى من مبلغ ممكن للمبلغ الأقصى في أي إقران. المفتاح إلى الخوارزمية هو فرز القيم من الأقل إلى أعظم. ثم إقران الأقل مع أعظم، وهكذا، حتى تصل إلى مركز الطلب.

مثال: 3، -2، 4، 5

الخوارزمية فرز القيم: -2، 3، 4، 5

ثم أزواج أولا مع الأخير: (-2، 5)

ثم أزواج التالي المتاحة أولا وأخيرا: (3، 4)

ينتهي منذ لا أزواج اليسار.

هذه خوارزمية جشعة وأحاول إثبات أنها صحيحة دائما باستخدام نهج "البكاء الجشع". مشكلتي هي أنني تكافح من أجل إظهار أن الحد الأقصى للمجموع في الخوارزمية هو دائما $ \ leq $ الأمثل الحد الأقصى للمبلغ. كان من المفترض أن يفترض نيتي التناقض أن الحد الأقصى الأمثل هو $ <$ الحد الأقصى للمجموع في الخوارزمية. لكنني لست متأكدا من كيفية العثور على تناقض. كيف يذهب هذا الدليل؟

Answer 1

هل تستطيع أن ترى لماذا $ \ max ((- 2) +5، 3 + 4) \ lt \ max (-2 + 3، 4 + 5) $ ؟

السبب بسيط. لأنه على الجانب الأيمن، لا يقترن الحد الأقصى للرقم 5 مع الحد الأدنى من العدد.

---

دع الأرقام هي $ a_1 \ le a_2 \ le \ le \ le \ le a_n $ . دع الأرقام يتم إقرانها بطريقة ما.

• إذا كان $ a_n $ يتم إقرانها مع $ a_1 $ ، لقد انتهينا في هذا جولة.

• افترض $ a_n $ مع $ a_j $ ، $ J \ not= 1 دولار . ثم $ a_1 $ "SPAN Class=" حاوية الرياضيات "> $ a_k $ لبعض $ k \ not= n $ . لذلك لدينا أزواج، $ \ {A_N، A_J \} $ و $ \ {a_1، a_k \} $ < / span>. مبالغ هذين الزوجين هي $ a_n + a_j $ و $ a_1 + a_k $ ، واحد كبير منها $ a_n + a_j $ .

  دعنا تبديل $ a_j $ و $ a_1 $ حتى $ a_n $ سوف يقترن مع $ a_1 $ ، و $ a_j $ الإرادة زوج مع $ a_k $ . مبالغ بين الأزواجين الجديدة هي $ a_n + a_1 $ و $ a_j + a_k $ ، كل من وهو في معظم $ a_n + a_j $ ، أي، واحد منهم، واحد منهم هو في معظم $ a_n + a_j $ < / span>. بعد التبديل، فإن الحد الأقصى للمبلغ من الأزواج التي تنطوي على $ a_n، a_j، a_k، a_1 $ لا تزيد. نظرا لأن أزواج أخرى تبقى كما هي، فبعد التبديل، لا يزيد الحد الأقصى للمبلغ من جميع أزواج.

مواصلة هذه العملية، وسوف نتأكد من إقران أكبر عدد متبقي مع أصغر عدد متبقي في كل جولة. لن يزيد الحد الأقصى للمبلغ من الأزواج في كل جولة. بعد جولات $ N / 2 $ ، سنصل إلى الاقتران حيث $ A_K $ مقترن مع $ a_ {n + 1-k} $ .

يمكنك أن ترى النهج المذكور أعلاه هو بالفعل "يبقى الجشع قديم".