سیب های در حال سقوط

[armita]

فرض کنید یک گاری دارید و یک تعدادی سیب هم هستن که با سرعت های مختلف در حال سقوطند !
در اول سرعت همه ی سیب ها و فاصله اشون تا زمین رو دارین
سرعت گاری رو هم می دونید .
چجوری حرکت کنیم تا بیشترین تعداد سیب رو جمع کنیم ؟
(خواهشا نیاین یه دفعه کل جواب رو بذارین اگر بلدین !)

 

[سروش ربیعی]

پاسخ : سیب های در حال سقوط

لطفاً به سؤالای پایینی جواب بدین تا بتونم کمکتون کنم:
سرعت گاری ثابته؟ تو یک بعد حرکت می‌کنه؟ اگه تو یه بعد حرکت می‌کنه، طول گاری مشخصه؟ طول صفحه متناهیه؟

این مسأله از نوع مسائل بهینه‌سازیه. اگه نمی‌خوای از تکنیک‌های هوش مصنوعی استفاده کنی باید یه رابطۀ والانس بین پارامترهای فاصلۀ سیب، سرعت سیب و فاصلۀ گاری تا نقطۀ سقوط سیب پیدا بکنی. خیلی ساده‌س کمیت بهینه‌سازیت می‌تونه این باشه: تعداد رسیدن های ممکن.
اما من توصیه می‌کنم همۀ جایگشت‌های «ممکن» برای ترتیب گرفتن سیب‌ها رو بریزی تو یه درخت. بعد خیلی ساده عمیق‌ترین پیمایش، یا یکی از عمیق‌ترین‌ها رو به عنوان جواب قبول کنی.
اگر چند تا جواب به دست اومد می‌تونی بازم کامل‌ترش کنی. مثلاً میتونی جوابی با کمترین جابه‌جایی گاری رو به عنوان جواب قبول کنی.

حله؟