الگوریتم حریصانه: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Haniyeh120 (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
Haniyeh120 (بحث | مشارکت‌ها) |
||
خط ۶۰:
==== '''[[مسئله کوله‌پشتی|مسئلهٔ کولهٔ پشتی]]:''' ====
[[پرونده:Knapsack.svg|بندانگشتی|250px|نمونه‌ای از مسئلهٔ کوله‌پشتی یک بعدی: چه جعبه‌هایی باید انتخاب شوند تا مقدار پول بیشینه شود اما وزن جعبه‌های مذکور بیشتر از ۱۵ کیلوگرم نشود؟ یک
ما n شی و یک کولهٔ پشتی داریم که هر شی دارای وزنی است؛ ظرفیت کولهٔ پشتی نیز محدود است. ما می‌خواهیم ارزش شی‌های قرار داده شده در کولهٔ پشتی ماکزیمم شود:
خط ۱۸۷:
تعریف: دو فعالیتی را سازگار می‌گوییم که با یکدیگر هم‌پوشانی نداشته باشند.
مسئله انتخاب فعالیت عبارت است از انتخاب یک زیرمجموعه با [[ماکزیمم]] اندازه از فعالیت‌هایی که هم‌پوشانی ندارند. برای مثال زیرمجموعهٔ s از فعالیت‌ها را در نظر بگیرید که آن‌ها را برحسب زمان پایان به ترتیب [[تابع یکنوا|صعودی]]
<source lang="python">
i -> 1 2 3 4 5 6 7 8 9 10 11
خط ۲۵۵:
روش‌های [[الگوریتم پریم|پریم]] و [[الگوریتم کراسکال|کروسکال]] دو روش مشهور تولید درخت پوشای کمینه از یک [[گراف وزن‌دار]] هستند که از روش حریصانه بهره می‌برند. منظور از درخت پوشای کمینه، [[درخت پوشا]]<nowiki/>یی از گراف است که مجموع وزن یال‌های آن کمتر یا مساوی مجموع وزن یال‌های سایر درخت‌های پوشای آن گراف است.<ref>{{پک|ابراهیم علایی فرادنبه - محمدرضا علایی|۱۳۹۲|ک=طراحی الگوریتم ایران|ص=265}}</ref>
[[پرونده:Huffman tree 2.svg|left|thumb|350px|درخت هافمن، ایجاد شده از تعداد تکرار حرف‌های جملهٔ «this is an example of a
| |||