سوال ۷۹ کنکور ارشد علوم کامپیوتر ۱۴۰۱
اهمیت
۰/۵
کدام مسئله یا مسائل از ۳ مسئله زیر دارای الگوریتم حریصانه (greedy) با زمان چندجملهای است؟ کولهپشتی ۰ و ۱ / کولهپشتی کسری / زیردرخت فراگیر (پوشای) کمینه (MST)
پاسخ صحیح: گزینهٔ C — فقط کولهپشتی کسری و زیردرخت فراگیر (پوشای) کمینه
پاسخ تشریحی
We check, for each of the three problems, whether a greedy strategy solves it optimally in polynomial time.
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#greedy#fractional-knapsack#0-1-knapsack#minimum-spanning-tree#np-hardness#polynomial-time