الگوریتم های حریص در C ++ (10 مشکل محبوب با راه حل)

با گذشت هر روز ، برنامه نویسان در تلاشند تا با استفاده از موارد زندگی روزمره ، راه حل هایی را برای مقابله با مشکلات پیچیده تدوین کنند. حتی در مصاحبه ها ، سؤالات مهم برنامه نویسی با زندگی روزمره ما ارتباط دارد. بسیاری از الگوریتم ها برای یافتن راه حل در اسرع وقت ایجاد می شوند. یکی از این الگوریتم ها الگوریتم حریص است. بیشتر در هنگام جستجوی راه حل فوری استفاده می شود و به پیامدهای آینده اهمیتی نمی دهید.

الگوریتم هایی مانند Divide and Conquer و حریص در مصاحبه ها محبوبیت پیدا می کنند. رویکرد برای حل یک سؤال با استفاده از الگوریتم حریص ، حول مفهوم یافتن راه حل بهینه سازی شده محلی در حداقل بازه زمانی می چرخد. سؤالاتی که در مورد این مفهوم می چرخد بیشتر مطرح می شود ، بنابراین باید همه چیز را در مورد این موارد درک کنید. در این وبلاگ ، ما همه چیز را در مورد این الگوریتم ها ، ساختار ، مزایا ، مضرات و 10 مشکل برتر با کد C ++ خود می دانیم. بنابراین ، بیایید به این موضوع شیرجه بزنیم و همه چیز را در مورد آنها درک کنیم.

الگوریتم حریص چیست؟

مشکلات بهینه سازی به حداکثر رساندن/به حداقل رساندن یک مقدار خاص توسط یک الگوریتم ویژه به نام الگوریتم حریص حل می شود. حال ، چرا ما فقط این نوع سؤالات را با این کار حل می کنیم؟خوب ، حل فقط این نوع سؤالات یک قانون سخت و سریع نیست ، اما نکته مهم این است که به انتخاب فوری کمک می کند. وقتی از الگوریتم حریص استفاده می کنیم ، ما فقط به دنبال یک راه حل بهینه شده محلی هستیم و نه یک جهانی ، که بیشتر ما را در قفس قرار می دهد. در بعضی موارد ، این رویکرد ممکن است در ابتدا راه حل مناسب را ارائه دهد ، اما در پایان ، ممکن است غیر ضروری به نظر برسد.

این رویکرد دارای شایستگی ها و دلهره های خود است. اگرچه ، این یک روش خوب برای حل مشکلات بهینه سازی است ، اما در بعضی موارد هنوز هم از برخی شرایط غافل است. بنابراین ، مشاهده هر مرحله در حین کار با این الگوریتم برای به دست آوردن بهینه ترین راه حل که از مجموعه داده های ارائه شده استفاده می شود ، مهم است.

بیایید این الگوریتم را با یک مثال درک کنیم.

نمونه شمارش سکه ها با استفاده از الگوریتم حریص

به ما سکه های خاصی داده می شود که به ارزش 1 ، 2 دلار ، 5 دلار و 10 دلار ارزش دارند. اکنون باید مقدار مشخص شده را با استفاده از این سکه ها حساب کنید.

مورد 1: 16 دلار

روش حریص مانند این خواهد بود.

• اولا ، ما 1 سکه را با قیمت 10 دلار می گیریم. بنابراین ، اکنون ما با 6 دلار کمتر هستیم.
• اکنون ، ما 1 سکه 5 دلار و بعد از آن ، 1 سکه 1 دلار خواهیم گرفت.

چرا ابتدا سکه 10 دلاری را انتخاب کردیم، می توانستیم سکه های دیگری را نیز انتخاب کنیم. چون ما حریصیمسکه ای را می گیریم که ارزش بیشتری دارد. در این مورد، پاسخ بسیار خوب بود. اگر مورد دیگری را بگیریم چه؟

مورد 2: 17 دلار

روال به شرح زیر خواهد بود:

• 1 سکه 10 دلاری بردارید. اکنون 7 دلار کمتر شده ایم.
• ما هیچ انتخاب دیگری نداریم، جز انتخاب 7 سکه 1 دلاری.

اکنون، این ایده چندان مطلوبی نیست. اینجاست که الگوریتم حریص شکست می خورد. از این رو، می توان گفت که استفاده از اینها برای راه حل های فوری عالی است، اما نه برای راه حل های بهینه شده در سطح جهانی.

ساختار اساسی یک الگوریتم حریص

در زیر به چند ویژگی از الگوریتم Greedy اشاره کرده ایم که به شما کمک می کند بدانید رویکردی که دنبال می کنید حریص است یا خیر:

1. لیستی از منابع مانند سکه ها، وظایف و غیره به ما داده می شود.
2. ما با بزرگترین/بزرگترین منبع با ارزش شروع می کنیم.
3. بعداً، ما به اضافه کردن منابع با ارزش بیشتر برای رسیدن به راه حل بهینه ادامه می دهیم.

مزایای الگوریتم حریص

1. این آسان تر برای پیاده سازی و درک است.
2. پیچیدگی زمانی این به طور قابل توجهی کمتر است.
3. اینها را می توان به راحتی برای یافتن راه حل بهینه برای یک مسئله پیچیده استفاده کرد.

معایب الگوریتم حریص

تنها عیب پیروی از این رویکرد این است که اهمیت راه حل بهینه سازی شده جهانی را نادیده می گیریم. در بیشتر موارد، ما معمولاً یک راه حل بهینه سازی محلی دریافت می کنیم و این ما را در حین مشاهده کل مجموعه داده، در یک مشکل قرار می دهد.

اجزای الگوریتم حریص

مولفه های کلی این رویکرد در زیر ذکر شده است:

1. Candidate Set: راه حل مشکلی که از مجموعه داده ایجاد شده است.
2. تابع انتخاب: تابعی است که تصمیم می گیرد آیا عنصر را می توان به عنوان راه حل اضافه کرد یا خیر.
3. تابع امکان سنجی: بررسی می کند که آیا عناصر انتخاب شده در تابع انتخاب و مجموعه نامزد امکان پذیر هستند یا خیر.
4. تابع هدف: مقداری را به راه حل اختصاص می دهد.
5. تابع راه حل: برای نزدیک کردن رسیدن به عملکرد کامل استفاده می شود.

کاربردهای الگوریتم حریص

1. یافتن کوتاه ترین مسیر با استفاده از Dijkstra.
2. یافتن حداقل درخت پوشا با استفاده از الگوریتم Prim یا الگوریتم Kruskal.
3. حل مسئله کوله پشتی کسری.

10 مشکل برتر الگوریتم حریص با کد ++C

از آنجایی که اصول اولیه الگوریتم های حریص را درک کرده اید، بیایید 10 مشکل برتر را که اغلب در دورهای فنی پرسیده می شوند، بررسی کنیم. برای سهولت شما، ما رویکرد و همچنین کد C++ مشکلات را ارائه کرده ایم.

1) مشکل انتخاب فعالیت

بیانیه مشکل: با زمان شروع و پایان آنها فعالیتهای N به شما داده می شود. با فرض اینکه یک شخص می تواند فقط در 1 فعالیت در یک زمان کار کند ، حداکثر تعداد فعالیتهایی را که می تواند در حداقل زمان انجام دهد پیدا کنید.

رویکرد به سمت راه حل: همانطور که ما با استفاده از رویکرد حریص آن را حل می کنیم ، انتخاب فعالیتی که در زمان کمتری انجام شود ، کاملاً واضح است. چرا؟این امر به این دلیل است که ما قادر خواهیم بود به جای تمرکز بر انجام فقط یک کار سنگین ، کارهای بسیاری را در یک زمان مشخص انجام دهیم. بنابراین ، ما باید وظایف را به ترتیب عدم کاهش انتخاب کنیم.

1. راه حل را با مرتب سازی آرایه های داده شده به ترتیب صعودی با استفاده از تکنیک مرتب سازی مورد نظر خود شروع کنید.
2. به خاطر داشته باشید که برای شروع فعالیت ها ، شخص باید با اولین کار شروع کند. این بدان معناست که مهم نیست که چه ورودی هایی به ما داده شده است ، اولین فعالیت همیشه اجرا می شود. چرا؟زیرا اگر می خواهید یک فعالیت واحد انجام دهید ، مهم نیست که کدام یک را انجام می دهید!
3. درک کنید که فرد فقط پس از تکمیل فعالیت قبلی قادر به انجام فعالیت های جدید خواهد بود. اگر شخص در آن زمان فعالیت قبلی را انجام می دهد ، مورد بعدی را رد کنید و حرکت کنید. بنابراین ، اگر زمان شروع آن بیشتر یا مساوی با زمان پایان فعالیت قبلی باشد ، مورد بعدی را انتخاب کنید.

مثال:

ورودی: شروع [] = ؛پایان [] =

خروجی: ،

توضیح: ما قبلاً فهمیدیم که اولین کار به هر کاری انجام می شود. بنابراین ، شارژ به آرایه راه حل اضافه می شود. با حرکت ، زمان پایان کار 0 با زمان شروع مقایسه می شود. اکنون ، از آنجا که کمتر از زمان پایان قبلی است ، ما حرکت می کنیم. باز هم مقایسه اتفاق می افتد و کار انتخاب می شود.

اجرای با کد C ++:

خروجی:

2) بهترین زمان برای خرید و فروش سهام

بیانیه مشکل: به شما قیمت های آرایه داده می شود [] که حاوی قیمت سهام در بعضی از روزها است. شما باید یک روز را برای خرید سهام و یک مورد دیگر برای فروش آن انتخاب کنید. روزهایی را که در آن خرید و فروش سهام را بازگردانید ، برگردانید.

رویکرد به سمت راه حل: در این سؤال ، شما نیازی به چیزی در مورد سهام ندارید ، رویکردی که ما ارائه می دهیم حتی برای مبتدیان نیز به اندازه کافی آسان است. اکنون کاملاً بدیهی است که وقتی می خواهید هر چیزی را خریداری کنید ، می خواهید کمترین قیمتی را که می توانید بپردازید. به همین ترتیب ، در حالی که همان کالاها را می فروشید ، می خواهید با فروش آن با قیمت بزرگتر ، سود خود را افزایش دهید. بنابراین ، شما برای افزایش سود خود حریص هستید. بنابراین ، بیایید ببینیم که چگونه با این سوال پیش می روید:

1. در اینجا ، مرتب سازی کار نمی کند زیرا شما باید تعداد روز را بدهید. بنابراین ، ابتدا حداقل ارزش سهام را از قیمت ها پیدا خواهید کرد [].
2. شاخص حداقل ارزش به روزی که سهام خود را خریداری می کنید تبدیل می شود.
3. برای فروش سهام ، باید پس از خرید سهام ، ارزش سهام را بررسی کنید.
4. از این رو ، یک حلقه را تا پایان شروع از خرید روز اجرا کنید و حداکثر مقدار سهام را در آرایه باقیمانده پیدا کنید.
5. اکنون ، ارزش خرید را از SellingDay و Voila کم کنید! شما جواب داده اید!

مثال:

ورودی:

خروجی: 5

توضیح: همانطور که در این رویکرد ذکر کردیم ، ابتدا کمترین عنصر را که 1 است ، در اینجا پیدا خواهید کرد. اکنون ، روز خرید 1 می شود. پس از آن ، ما حداکثر ارزش سهام را در روزهای بعد از آن جستجو می کنیم. بنابراین ، روز فروش روز با 6 ارزش می شود. اکنون ، ما تفاوت بین هر دو را پیدا می کنیم و 5 را به عنوان خروجی خود بدست می آوریم. نگاهی به تصویر زیر بیندازید.

اجرای با کد C ++

خروجی:

3) مشکل توالی کار

بیانیه مشکل: به شما آرایه ای داده می شود که به شما شغل های خاصی ، مهلت آنها و سود حاصل از تکمیل آنها به موقع داده می شود. هر شغل حداقل یک واحد زمان طول می کشد. شما باید حداکثر سود خود را با تکمیل شغل در یک زمان خاص بازگردانید.

رویکرد به سمت راه حل: از آنجا که ما باید حداکثر کار را در حداقل زمان انجام دهیم ، با رویکرد حریص خواهیم رفت. ما مشاغل را در کاهش نظم سود آنها مرتب خواهیم کرد. اکنون ، ما هر کار را طی خواهیم کرد و مهلت آن را بررسی خواهیم کرد. اگر در آرایه ما باشد ، فضایی خالی برای تکمیل آن کار خاص قبل از زمان یا حتی در آن زمان وجود دارد ، ما آن را می گیریم و سود آن را به متغیر نتیجه خود اضافه می کنیم. در غیر این صورت ، ما به سمت بعدی حرکت خواهیم کرد. مراحل زیر را دنبال کنید:

1. مشاغل را به ترتیب صعودی سود خود مرتب کنید.
2. شروع به گذر از مشاغل یک به یک کنید.
3. اگر در یک کار ، یک شکاف زمانی خالی داشته باشید و سود آن بیشتر باشد ، آن کار را انجام می دهید و سود آن را به متغیر نتیجه خود اضافه می کنید.
4. اگر اینطور نیست ، شما به سمت بعدی حرکت خواهید کرد.

مثال:

خروجی:

توضیح: ابتدا آرایه ای از عناصر را با توجه به سود آنها مرتب کردیم. اکنون ، اولین مورد بالاترین سود را دارد که 40 است ، بنابراین ما این کار را گرفتیم و از آنجا که مهلت آن به عنوان 1 ذکر شده است ، ما می توانیم این کار را در 0-Time Frame انجام دهیم یا 1. بنابراین ، ما این کار را در 0. انجام دادیم. اکنون ، مابه جلو بروید و دیگری را ببینید که بازه زمانی آن 1 است. اما ، ما مجبور شدیم از آن غافل شویم زیرا ما در حال انجام کار در آن (0) بازه زمانی هستیم. اکنون ، هنگامی که ما به مرحله بعدی رسیدیم ، می بینیم که می توان آن را در 4 به پایان رساند ، بنابراین ، یا 0،1،2 یا 3. بنابراین ، ما آن را گرفتیم و آخرین موردی را که فقط 1 به عنوان بازه زمانی خود داشت ، نادیده گرفتیم.

اجرای با کد C ++:

خروجی:

4) مشکل کوله پشتی کسری

بیانیه مشکل: به شما وزن و مقادیر N موارد داده می شود. شما باید این موارد را در یک کوله پشتی از ظرفیت W قرار دهید به گونه ای که مقدار نهایی کوله پشتی حداکثر باشد. برای دستیابی به بهینه ترین پاسخ می توانید موارد را به کسری تقسیم کنید.

رویکرد به سمت راه حل: از آنجا که از شما خواسته می شود حداکثر مقدار کوله پشتی را پیدا کنید ، باید به طور خودکار برای استفاده از رویکرد حریص اعتصاب کند. حال ، ما باید در ظرفیت ثابت آن مقدار کوله پشتی را به حداکثر برسانیم. این بسیار ساده است که ما آن عنصری را انتخاب خواهیم کرد که وزن آن کمتر است اما ارزش آن بیشتر است. چرا؟از آنجا که ما در وزن محدود به حداکثر مقدار نیاز داریم ، اگر مقدار بیشتری را با وزن کمتری انتخاب کنیم ، به طور خودکار قادر خواهیم بود عناصر بیشتری را در کوله پشتی قرار دهیم. بنابراین ، دستیابی به بیشترین ارزش ممکن.

بیایید مراحلی را که باید دنبال کنید ببینیم:

1. شما به عناصری با وزن کم و ارزش بیشتر نیاز دارید. بنابراین ، ما نسبت این دو را برای هر عنصر محاسبه می کنیم.(نسبت = مقدار/وزن)
2. از آنجا که ابتدا به عناصر با ارزش نیاز داریم ، این نسبت ها را به ترتیب صعودی مرتب می کنیم.
3. اکنون ، شما از طریق عناصر تکرار می شوید و بررسی می کنید که آیا وزن آن عنصر کمتر یا مساوی با حداکثر وزن کوله پشتی است. اگر بله ، آن را به پاسخ خود اضافه کنید. در غیر این صورت ، حرکت کنید.

مثال:

Input: , ,>؛W = 50

خروجی: 240

توضیح: اکنون ، وزن کوله پشتی 50 کیلوگرم است ، بنابراین باید عناصر با وزن برابر با این اضافه کنید. بنابراین ، ما می توانستیم عناصر 2 و 3 را در نظر بگیریم اما این 1 را از بین می برد. از این رو ، ما 1 و 2 را گرفتیم و سپس یک قسمت کسری (2/3) از عنصر 3 گرفتیم. بنابراین ، گرفتن حداکثر پاسخ ممکن. همچنین می توانید به تصویر زیر نگاهی بیندازید.

اجرای با کد C ++:

خروجی:

5) حداقل تعداد سکه ها

بیانیه مشکل: به ما ارزش V داده می شود و باید تغییر آن را در سکه های هندی ارائه دهیم. اکنون فرقه ها 1 ، 2 ، 5 ، 10 ، 20 ، 50 ، 100 ، 200 ، 500 ، 2000 هستند. نتیجه باید حاوی کمترین تغییر ممکن از مقدار داده شده باشد.

رویکرد به سمت راه حل: باز هم ، از آنجا که ما باید در ازای مقدار V حداقل تعداد ممکن سکه را پیدا کنیم ، ما از حریص استفاده خواهیم کرد. بنابراین ، ما با حداکثر سکه ارزشمند که کمتر از یا برابر V. است ، شروع خواهیم کرد. اکنون مقدار سکه انتخاب شده را از مقدار داده شده کم می کنیم. برای مقدار باقیمانده ، ما مجدداً سکه با ارزش را جستجو می کنیم و آن را به جواب اضافه می کنیم. مراحل زیر را دنبال کنید:

1. بزرگترین سکه با ارزش را در بین داده ها پیدا کنید.
2. آن را به نتیجه اضافه کنید و از V.
3. مراحل فوق را تکرار کنید تا مقدار کامل را پیدا کنید.

مثال:

ورودی: V = 70

خروجی: 2

توضیح: برای به دست آوردن تغییر 70 ، ما به یک یادداشت از 50 و دیگری از 20 نیاز خواهیم داشت.

اجرای با کد C ++:

خروجی:

6) حداقل مشکل پلتفرم

بیانیه مشکل: زمان ورود و عزیمت قطارهای خاص به شما داده می شود. شما باید حداقل تعداد سیستم عامل ها را در ایستگاه پیدا کنید تا هیچ قطار با برنامه های یکدیگر درگیری نباشد.

رویکرد به سمت راه حل: در این سؤال نیز باید حداقل تعداد سیستم عامل ها را پیدا کنیم ، از این رو برای یافتن جواب از رویکرد حریص استفاده خواهیم کرد. ما زمان قطار را بررسی خواهیم کرد و نتیجه متغیر را به صورت اولیه انجام می دهیم. اگر در هر جایی اتفاق بیفتد ، نتیجه را به 1. افزایش می دهیم. بنابراین ، در پایان ، حداقل تعداد سیستم عامل های مورد نیاز را دریافت خواهیم کرد.

مثال:

ورودی: arr [] = ؛dep [] =

خروجی: 1

توضیح: ما با زمان عزیمت قطار اول شروع خواهیم کرد و بررسی خواهیم کرد که آیا قطار بعدی بین برنامه اول وارد می شود یا خیر. از آنجا که در اینجا ، چیزی شبیه به آن اتفاق نمی افتد ، ما فقط 1 پلتفرم خواهیم داشت.

اجرای با کد C ++:

خروجی:

7) مشکل پمپ بنزین

بیانیه مشکل: به شما 2 آرایه عدد صحیح گاز [] و هزینه [] داده می شود. در یک مسیر دایره ای پمپ بنزین N وجود دارد. هر ایستگاه مقدار خاصی از گاز دارد که در وسیله نقلیه دوباره پر می شود و همچنین برای رسیدن به محل بعدی به مقدار خاصی از سوخت نیاز دارد. شما باید نقطه شروع را پیدا کنید تا بتوانید تمام ایستگاه های اطراف مدار را در جهت عقربه های ساعت طی کنید.

رویکرد به سمت راه حل: شما باید از آن پمپ بنزین که دارای گاز است ، شروع کنید که می تواند شما را به یک قسمت بعدی و بعد از آن ، در اطراف همه ایستگاه ها پس از بازدید از هر یک از آنها منتقل کنید. بنابراین ، ما شروع به بررسی از فهرست اول خواهیم کرد تا احتمال آن را بررسی کرده و به سمت بعدی حرکت کنیم.

مثال:

ورودی: گاز [] = ؛هزینه [] =

خروجی: 3

توضیح: شما با 3 پمپ بنزین شاخص 3 شروع خواهید کرد. اکنون ، با 4 لیتر گاز حرکت خواهید کرد و به یکی دیگر خواهید رسید. بنابراین ، برای رسیدن به این که شما 1 لیتر را خرج کرده و به دست می آورید.

اجرای با کد C ++:

خروجی:

8) طناب های "N" را با حداقل هزینه وصل کنید

بیانیه مشکل: به شما طناب هایی با طول های مختلف داده می شود. اکنون ، شما باید آن طناب ها را به یک واحد متصل کنید. حداقل هزینه پیوستن به تمام طناب ها را به یک واحد پیدا کنید. فرض کنید که هزینه پیوستن به طناب برابر است با مجموع طول آنها.

رویکرد به سمت راه حل: شهود این سؤال این است که ما ابتدا آن دو طناب را اضافه خواهیم کرد که هزینه پیوستن آنها حداقل به وجود می آید. پس از آن ، ما دوباره به آن دو نفر می پیوندیم که هزینه پیوستن آنها کمترین هزینه است. به همین ترتیب ، ما از طریق تمام طناب ها تکرار خواهیم کرد. برای این کار ، ما از یک صف اولویت استفاده خواهیم کرد. مراحل زیر را دنبال کنید:

1. در صف اولویت از A-Heap استفاده کنید.
2. از 2 عنصر برتر استفاده کنید (حداقل آنها هستند) و آنها را اضافه کنید. مبلغ به نتیجه اضافه می شود.
3. اکنون ، شما با یک عنصر کمتر مانده اید. باز هم ، همان رویکرد را دنبال کنید.
4. این کارها را ادامه دهید تا یک پاسخ واحد به دست بیاید.

مثال:

ورودی:

خروجی: 36

توضیح: در مرحله اول ، یک متغیر به نام نتیجه = 0 را آغاز کنید. به یاد داشته باشید که هزینه پیوستن طناب ها را به این متغیر اضافه کنید. اکنون ، طناب های طول 4 و 2 را به هم وصل خواهیم کرد. بنابراین ، نتیجه = 6. اکنون ، ما مانده ایم. بنابراین ، دوباره 2 عنصر حداقل را از آرایه می گیریم و آنها را اضافه خواهیم کرد. نتیجه = 6+11 اکنون ، ما به عناصر باقیمانده 11 و 8 می پیوندیم ، بنابراین ، در نهایت نتیجه = 6+11+19. بنابراین ، نتیجه نهایی 36 است.

برای درک ساده تر ، تصویر زیر را رعایت کنید.

اجرای با کد C ++:

خروجی:

9) فواصل همپوشانی را ادغام کنید

بیانیه مشکل: به شما فواصل زمانی داده می شود. شما باید فواصل همپوشانی را در یک ادغام کنید و فواصل منحصر به فرد را به عنوان پاسخ برگردانید.

رویکرد به راه حل: ما باید فواصل زمانی را که همپوشانی دارند با هم ادغام کنیم. چگونه بررسی می کنید که آیا یک بازه با دیگری همپوشانی دارد یا خیر؟خیلی ساده! شما بررسی کنید که آیا حد داخلی آن کمتر از حد بیرونی قبلی است یا خیر. اگر درست باشد، بله، با هم همپوشانی دارند، در غیر این صورت، نه! مراحل زیر را دنبال کنید:

1. همه فواصل را به ترتیب صعودی زمان شروع آنها مرتب کنید.
2. شروع به تکرار در تمام فواصل.
3. اگر بازه خاصی با فاصله قبلی همپوشانی دارد، آن را با فاصله قبلی ادغام کنید و جلو بروید.

مثال:

خروجی:

توضیح: فواصل را به ترتیب صعودی زمان شروع آنها مرتب می کنیم و شروع به پیمایش می کنیم. ما شروع به بررسی می کنیم و متوجه می شویم که همه آنها را می توان با آنها ادغام کرد، بنابراین، این پاسخ ما است. تصویر زیر را بررسی کنید.

اجرای با کد C ++:

خروجی:

10) برنامه ریزی دو شهر

بیان مشکل: 2n نفر توسط یک شرکت مصاحبه می کنند. به شما هزینه های آرایه[] داده می شود که حاوی [aCost[i]، bCosr[i]] است. هزینه پرواز یک نفر به شهر a aCost[i] و هزینه پرواز او به شهر b bCost[i] است. شما باید حداقل هزینه را برای پرواز افراد به یک شهر پیدا کنید، به طوری که n نفر در هر شهر وارد شوند.

رویکرد به مسئله: از آنجایی که 2n نفر وجود دارد و شما در هر شهر به n نفر نیاز دارید، به این معنی است که نیمی از مردم به شهر a و نیمی دیگر به شهر b خواهند رفت. اکنون، همانطور که هزینه های پرواز افراد برای هر دو شهر به شما داده می شود. بنابراین، شما باید حداقل هزینه رفتن به یک شهر خاص را برای یک فرد پیدا کنید. چطوری انجامش بدهم؟

1. هزینه های داده شده را به ترتیب صعودی مرتب کنید.
2. اکنون به نصف نفر در یک شهر و نیمی دیگر در شهر دوم نیاز دارید.
3. بنابراین، تعداد کل افراد را بر 2 تقسیم کنید. نیمه اولیه به شهر a می رود و بعداً از شهر b دیدن می کند.

مثال:

ورودی: [[10،20]، [30،200]، [400،50]، [30،20]]

خروجی: 110

توضیح: وقتی آرایه را به ترتیب صعودی مرتب می کنیم، [[10،20]، [30،200]، [30،20]، [400،50]] به دست می آید. بنابراین، دو نفر اول از شهر دیدن خواهند کرد، بنابراین، نتیجه 10+30=40 خواهد بود و دومی به شهر b می رود، با هزینه 50+20=70. بنابراین 40+70=110

اجرای با کد C ++:

خروجی:

نتیجه

شرکت های بزرگ فناوری به دلیل کاهش سریع منابع و زمان بر روی بهینه سازی تمرکز می کنند. یک الگوریتم حریص، بدون شک، در چنین سناریوهایی به دستیابی به بهترین راه حل بهینه محلی با پیچیدگی زمانی کمتر کمک می کند. اگرچه، در برخی موارد، یک راه حل بهینه شده در سطح جهانی مورد نیاز است، اما هنوز هم، با استفاده از این رویکرد، زمینه خوبی برای حل مسائلی مانند موارد فوق وجود دارد. برای طیف وسیعی از مشکلات به خوبی کار می کند. بنابراین، تمرین چنین سوالاتی می تواند برای شما مفید باشد!