مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.

====== حریصانه ======
در این روش از یک حالت ابتدایی شروع می‌کنیم و هر بار با انتخابی که بیشترین سود را به ما می‌دهد به جواب بهینه می‌رسیم. 
اثبات اینکه مسأله‌ای با این روش قابل حل است لزوما ساده نیست.

برای مثال ساده‌ای از این الگوریتم، فرض کنید می‌خواهید 1400 تومان پرداخت کنید و از همه‌ی اسکناس‌ها به میزان دلخواه در اختیار دارید، اما می‌خواهید کمترین تعداد اسکناس را به کار ببرید. به صورت حریصانه بزرگترین اسکناس کوچکتر از مقدار مورد نظر را پیدا می‌کنید (1000 تومان) و بقیه آن را هم با همین روش خرد می‌کنید (۲ اسکناس ۲۰۰ تومانی). روش حریصانه برای حالتی که مثلاً اسکناس 700 تومانی وجود داشته باشد کار نمی‌کند چون در این صورت با دو اسکناس ۷۰۰ تومانی می‌توانستیم این مبلغ را پرداخت کنیم.

از این روش برای مسایلی که [[الگوریتم:برنامه‌ریزی_پویا|برنامه‌ریزی پویا]] و [[الگوریتم:جستجوی_کامل|جستجوی کامل]] زمان زیادی می‌برند استفاده کنید یا برای مسایلی که با حل آنها با این روش، از قبل آشنایی دارید.

مسایل زیر با روش حریصانه حل می‌شوند:
  * [[http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=greedyAlg|زمان‌بندی کارها]]
  * [[http://www.algorithmist.com/index.php/Greedy|کوله‌پشتی کسری]]
===== مسایل نمونه =====
۱- شما یک نوار ویدئویی دارید و می‌خواهید هر آخر هفته با دوستانتان یک فیلم کوتاه ببینید. می‌دانید هر هفته یک نفر از پنجره وارد می‌شود و نوار ویدئو را به اول آن برمی‌گرداند؛ در نتیجه شما باید هر هفته نوار را جلو بزنید تا به فیلم آن هفته برسید. باید فیلم‌ها را به چه ترتیبی بچینید که جمع زمانی که صرف جلو زدن فیلم‌ها می‌کنید کمینه شود؟ فرض کنید طول فیلم‌ها به صورت یک دنباله $L_i; 1\leq i \leq n$ داده شده است.

جواب: فیلم‌ها را به ترتیب از کوتاهترین به بلندترین مرتب کنید. می‌توانید از تابع مرتب‌سازی کتابخانه $algorithm.h$ برای این کار استفاده کنید.

۲-طوفان در همه‌ی طویله‌های با ظرفیت یک گاو را برده است. حداکثر $M\ (1\leq M \leq 50)$ تخته چوب می‌توانیم بخریم و $S\ (1\leq S \leq 200)$ طویله داریم و $C\ (1\leq C \leq S)$ حداکثر تعداد طویله‌هایی است که در آنها گاو است و شماره هر طویله را هم داریم. بیشینه‌ی تعداد طویله‌هایی که می‌توانیم برای آنها در بزنیم چقدر است؟ عرض طویله‌ها با هم برابر است و طویله‌ها در یک ردیف هستند، یعنی می‌توان طویله‌های متوالی را با چوب به طول مجموع عرض آنها پوشاند.

جواب: یک آرایه به تعداد طویله‌ها بگیرید و طول تکه‌چوب‌های لازم برای طویله‌های متوالی را حساب کنید. $M$ طولانی‌ترین تکه‌چوب‌ها باید خریداری شوند. جمع طول آنها تعداد طویله‌هایی است که می‌توانیم برای آنها در بسازیم.

[[http://activities.tjhsst.edu/sct/lectures/1213/Greedy_Bronze_Lecture.pdf|منبع سوالات]]

مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه