اولویت سود

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

مثلا :

7 1 1 3 2 3 5 3 4 20 4 3 18 5 2 0 6 1 6 7 2 30 74 اولین کار تکمیل شده وظیفه-6 با سود 6 خواهد بود. دومین کار تکمیل شده وظیفه-7 با سود خواهد بود. از 30. سومین کار تکمیل شده، task-4 با سود 18 خواهد بود. آخرین کار تکمیل شده، task-3 با سود 20 خواهد بود. بنابراین حداکثر سود = 6+30+18+20=74.

مشاهده:

ورودی: پنج شغل با مهلت ها و سودهای زیر ID مهلت سود x 2 100 y 1 19 z 2 27 u 1 25 v 3 15 خروجی: در زیر دنباله حداکثر سود مشاغل z, x, v آمده است برای حل این مشکل، مشاغل داده شده عبارتند ازبر اساس سود خود به ترتیب نزولی مرتب شده اند. از بین کارهای داده شده، ابتدا x را انتخاب می کنیم، زیرا در مهلت آن تکمیل می شود و حداکثر سود را می دهد. در مرحله بعد، z انتخاب می شود زیرا در مقایسه با y سود بیشتری می دهد. y را نمی توان انتخاب کرد زیرا مهلت آن به پایان رسیده است. کار u کنار گذاشته می شود زیرا نمی توان آن را در مهلت مقرر اجرا کرد. v انتخاب می شود زیرا می تواند در مهلت مقرر تکمیل شود. بنابراین، راه حل دنباله ای از مشاغل (z, x, v) است که در مهلت خود تکمیل می شوند و حداکثر سود را به همراه دارند. سود کل 100+ 27+15 =142.

رویکرد حل:

1. همه مشاغل داده شده را به ترتیب کاهش سود آنها مرتب کنید.
2. بر روی مشاغل به ترتیب کاهش سود تکرار کنید. برای هر شغل، موارد زیر را انجام دهید:
3. Find a time slot i, such that slot is empty and i>>
4. اگر چنین i وجود ندارد، کار را نادیده بگیرید.

راه حل ها:

#include #define MAX 1002 typedef struct Jobکار؛void jobSequencingWithDeadline(Job jobs[], int n); int minValue(int x, int y)int main (void)دمای کار؛int i, j; برای (i = 1; iمشاغل[j]. سود)>> jobSequencingWithDeadline(jobs, n); retu 0;>void jobSequencingWithDeadline(Job jobs[], int n)dmax)>برای (i = 1؛ i برای (i = 1؛ i = 1)k--;>if(filledTimeSlot == dmax)> maxprofit = 0; for(i = 1; i printf("%d
", maxprofit);>

#include #include using namespace std; ساختن کار; مقایسه ابله (شغل الف، شغل ب)b.profit);>int printJobScheduling (Job arr[], int n)>>بازگشت maxpro;// چاپ نتیجه // برای (int i=0; i int main()>nشغل arr[n]; برای (int i=0; i>arr[i].id>>arr[i].dead>>arr[i]. سود; کوت

واردات java. util.*; وارد کردن java. util. ArrayList; وارد کردن java. util. Arrays. واردات java. util. Collections. کلاس JobSequencingProblemشغل عمومی (شناسه بین المللی، مهلت بین المللی، سود بین المللی)>اصلی خالی استاتیک عمومی (رشته[] آرگ ها)Collections.sort(jobs); jobSequencing.printJobSequence(jobs, jobs.size());>Private void printJobSequence (کارهای ArrayList، اندازه int)= 0; j--)>>int ans=0; برای (int i = 0; iSystem.out.println(ans);>>

[forminator_quiz>

در این مقاله سعی شده است مفهوم الگوریتم Greedy مورد بحث قرار گیرد. امیدوارم این وبلاگ به شما در درک و حل مشکل کمک کند. برای تمرین مشکلات بیشتر روی الگوریتم Greedy می توانید MYCODE | را بررسی کنیدبرنامه نویسی رقابتی

برچسب شده الگوریتم، حریص، الگوریتم حریص، مصاحبه