مسابقه برنامه‌نویسی پیتزا رباتیک: نتایج
پیتزا رباتیک یک مسابقه برنامه‌نویسی و ریاضی دانش‌آموزی آنلاین هست که بهمن‌ماه ۹۷ در پایلی و با همراهی خانه ریاضیات اصفهان برگزار شد.
در این مسابقه برنامه‌نویسی، دانش‌آموزان باید برنامه‌ای می‌نوشتند که به یک شرکت نوپای پیتزا، به نام پیتزا رباتیک، کمک کند که بهترین سود و سرویس به مشتریان را داشته باشد. پیتزا رباتیک از ربات‌ها برای تهیه و تحویل پیتزا استفاده میکنه.
مشتری‌های پیتزا رباتیک پیتزای دلخواهشون را به هر قیمتی که می‌خواهند سفارش می‌دهند. پیتزا رباتیک میتونه هر کدام را که خواست قبول یا رد کنه. اما آنهایی که پذیرفت را باید تا یک مدت زمان مشخص تحویل دهد.
پیتزا رباتیک اگر هیچ سفارشی را قبول نکنه، هیچ سودی نمیکنه. از طرف دیگر، اگر همه سفارش‌ها را قبول کنه به احتمال زیاد ضرر کلانی میکنه. پیتزا رباتیک به برنامه‌ای نیاز داشت که بهشون بگه کدام یک از سفارش‌ها را قبول کنه. این برنامه‌ای هست که دانش‌آموزان براشون نوشتن.
جزییات مسأله مسابقه را میتونی اینجا ببینی.
تعریف مسأله از دیدگاه علوم کامپیوتر
مسأله مسابقه یکی از حالت‌های مسأله معروف کوله‌پشتی (Knapsack Problem) در علوم کامپیوتر هست. در تخصیص منابع (که برای ما می‌شود یک ربات پرنده) با محدودیت‌های عملیاتی (که برای ما می‌شود محدودیت زمانی تحویل پیتزا به مشتریان)، با این مسأله روبرو هستیم.
مسأله کوله‌پشتی کاربرد بسیار گسترده‌ای در بسیاری از صنایع دارد. رمزنگاری، انتخاب سرمایه‌گذاری، و بهره‌بردای شبکه توزیع برق تنها چند نمونه از این صنایع هستند.
در حل مسأله، دو معیار دارای اهمیت ویژه‌ای هستند و برای رتبه‌بندی شرکت‌کنندگان مسابقه در نظر گرفته شدند. به ترتیب اهمیت:
دقت: اینکه آیا برنامه جواب بهینه برای هر مورد به دست می‌آورد یا نه.
سرعت: اینکه برنامه برای پیدا کردن جواب چقدر زمان می‌برد.
رتبه‌های اول تا سوم بر اساس این معیارها تعیین شدند. جزییات برنامهها و عملکرد هر یک بر روی یک مجموعه از ۶ مورد گوناگون در انتهای خواندنی آورده شده است. اینجا میتونی راه‌حل گوگل (برنامه‌نویسی پویا) برای حل مسأله کوله‌پشتی را هم ببینی.
رتبه‌بندی
رتبه اول: نرگس منتظری با یک الگوریتم بازگشتی (recursive algorithm)
نرگس منتظری از مدرسه فرزانگان امین ۱ اصفهان موفق به نوشتن برنامه‌ای بازگشتی برای حل مسأله شد (فایل برنامه). رهیافت برنامه‌نویسی پویا در واقع حالت بهبودیافته این الگوریتم است.
این برنامه همیشه جواب بهینه را به دست می‌آورد. سرعت برنامه برای موارد با تعداد سفارش‌های کم تا متوسط (تا تقریبا ۴۰ سفارش) بالاست. اما بعد از آن سرعت برنامه به طور تصاعدی کاهش می‌یابد.
رتبه دوم: مهدی کریمی با یک الگوریتم حریصانه (greedy algorithm)
مهدی کریمی از مدرسه ابوذر اصفهان با رهیافت الگوریتم حریصانه در مسابقه شرکت کرد (فایل برنامه).
این برنامه معمولا جواب بهینه را به دست می‌آورد اما این تضمین‌شده نیست. سرعت برنامه همیشه و برای هر تعداد سفارشی بالا است. این یک مزیت بزرگ برای حالت‌هایی از مسأله کوله‌پشتی با تعداد انتخاب‌های زیاد هست.
رتبه سوم: بهفر باقری با یک الگوریتم بر پایه ارزیابی همه زیرمجموعه‌ها (enumeration)
بهفر باقری از مدرسه امام خمینی شاهین‌شهر برنامه‌ای نوشت که همه زیرمجموعه‌های ممکن را با استفاده از ماژول itertools تشکیل داده و ارزیابی می‌کند (فایل برنامه).
این برنامه همیشه جواب بهینه را به دست می‌آورد. اما به دلیل سرعت کم (هزینه محاسباتی بسیار بالا)، تنها برای موردهای با تعداد سفارش کم قابل استفاده است.
تقدیر و جمع‌بندی
ما به همه دانش‌‌آموزانی که برای حل مسأله این مسابقه تلاش کردند تبریک می‌گوییم. امیدوار هستیم که این مسابقه تجربه‌ای هیجان‌انگیز و آموزنده برای همه بوده باشد. این هدف اصلی ما بوده است.
از آنجایی که همه نفرات برتر از اصفهان هستند، تقدیرنامه و یک هدیه به رسم یادگار به صورت حضوری در خانه ریاضیات اصفهان به آنها تقدیم شد.
شرکت فرادرس هم هدیه‌ای در قالب اعتبار خرید برای دریافت رایگان هر کدام از صدها دوره آموزشی آنها به نفرات برتر اهدا نمود.
پیوست‌ها
عملکرد برنامهها روی ۶ مورد گوناگون
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
case = 'P1' max_total_time = 15 # minute orders = [{'id': 1, 'x': -1590, 'y': 1780, 'profit': 5.7}, {'id': 2, 'x': 1780, 'y': 930, 'profit': 6.8}, {'id': 3, 'x': -1630, 'y': 940, 'profit': 3.0}, {'id': 4, 'x': -1270, 'y': 50, 'profit': 3.6}, {'id': 5, 'x': -290, 'y': 1850, 'profit': 5.4}, {'id': 6, 'x': -1710, 'y': -320, 'profit': 7.6}, {'id': 7, 'x': -1030, 'y': -2220, 'profit': 5.3}, {'id': 8, 'x': -2470, 'y': 1440, 'profit': 5.6}, {'id': 9, 'x': 980, 'y': 1800, 'profit': 8.4}, {'id': 10, 'x': 2490, 'y': 2360, 'profit': 6.3}] # Name, total_net_profit, actual_total_time, accepted_orders_id & run time # NM: 6.9 14.99 [2, 6] & Time: 1 s # MK: 6.9 14.99 [2, 6] & Time: 1 s # BB: 6.9 14.99 [2, 6] & Time: 1 s # ---------- case = 'P2' max_total_time = 15 # minute orders = [{'id': 1, 'x': 1870, 'y': -2300, 'profit': 4.8}, {'id': 2, 'x': 1660, 'y': -760, 'profit': 9.2}, {'id': 3, 'x': -200, 'y': 40, 'profit': 7.3}, {'id': 4, 'x': 1640, 'y': 1310, 'profit': 7.9}, {'id': 5, 'x': 200, 'y': -1330, 'profit': 5.4}, {'id': 6, 'x': 620, 'y': -40, 'profit': 6.8}, {'id': 7, 'x': -170, 'y': 1040, 'profit': 3.6}, {'id': 8, 'x': 690, 'y': 430, 'profit': 8.2}, {'id': 9, 'x': 950, 'y': 1450, 'profit': 6.6}, {'id': 10, 'x': -1170, 'y': 990, 'profit': 9.8}, {'id': 11, 'x': 520, 'y': 1910, 'profit': 6.9}, {'id': 12, 'x': -150, 'y': 2390, 'profit': 7.7}, {'id': 13, 'x': 1320, 'y': 1010, 'profit': 4.7}, {'id': 14, 'x': 1450, 'y': -1760, 'profit': 3.9}, {'id': 15, 'x': -1500, 'y': -1060, 'profit': 9.6}, {'id': 16, 'x': -1360, 'y': 190, 'profit': 3.1}, {'id': 17, 'x': -2080, 'y': -660, 'profit': 3.0}, {'id': 18, 'x': 1240, 'y': -950, 'profit': 8.5}, {'id': 19, 'x': -2330, 'y': 1100, 'profit': 5.5}, {'id': 20, 'x': -1940, 'y': 1760, 'profit': 6.4}] # NM: 25.76 12.68 [3, 6, 8, 10] & Time: 1 s # MK: 25.76 12.68 [3, 6, 8, 10] & Time: 1 s # BB: 25.76 12.68 [3, 6, 8, 10] & Time: 6 s # ---------- case = 'P3' max_total_time = 30 # minute orders = [{'id': 1, 'x': -210, 'y': 2180, 'profit': 7.1}, {'id': 2, 'x': 1460, 'y': 1710, 'profit': 8.6}, {'id': 3, 'x': -2150, 'y': 310, 'profit': 4.0}, {'id': 4, 'x': 130, 'y': 2320, 'profit': 3.6}, {'id': 5, 'x': 660, 'y': 1460, 'profit': 8.8}, {'id': 6, 'x': 140, 'y': -620, 'profit': 4.7}, {'id': 7, 'x': 1910, 'y': 1800, 'profit': 9.7}, {'id': 8, 'x': 880, 'y': -450, 'profit': 4.1}, {'id': 9, 'x': -1810, 'y': -80, 'profit': 3.0}, {'id': 10, 'x': 2110, 'y': -570, 'profit': 7.8}, {'id': 11, 'x': 100, 'y': 970, 'profit': 8.8}, {'id': 12, 'x': 120, 'y': -60, 'profit': 3.4}, {'id': 13, 'x': 610, 'y': -20, 'profit': 4.7}, {'id': 14, 'x': 270, 'y': 2010, 'profit': 7.0}, {'id': 15, 'x': -80, 'y': -1940, 'profit': 5.5}, {'id': 16, 'x': 640, 'y': -1320, 'profit': 7.5}, {'id': 17, 'x': -10, 'y': -160, 'profit': 3.7}, {'id': 18, 'x': 1180, 'y': -1270, 'profit': 6.9}, {'id': 19, 'x': -2110, 'y': 1930, 'profit': 4.4}, {'id': 20, 'x': 1960, 'y': -1820, 'profit': 8.9}, {'id': 21, 'x': 1910, 'y': -650, 'profit': 3.6}, {'id': 22, 'x': -2290, 'y': -1430, 'profit': 8.6}, {'id': 23, 'x': 900, 'y': -60, 'profit': 8.8}, {'id': 24, 'x': 90, 'y': -1160, 'profit': 3.2}, {'id': 25, 'x': -1780, 'y': -120, 'profit': 9.5}, {'id': 26, 'x': -1950, 'y': -2430, 'profit': 8.7}, {'id': 27, 'x': -2030, 'y': -2420, 'profit': 4.4}, {'id': 28, 'x': -1620, 'y': -660, 'profit': 4.7}, {'id': 29, 'x': 890, 'y': -1410, 'profit': 9.1}, {'id': 30, 'x': -1320, 'y': 740, 'profit': 7.6}, {'id': 31, 'x': -10, 'y': -1330, 'profit': 7.8}, {'id': 32, 'x': -270, 'y': -1340, 'profit': 8.1}, {'id': 33, 'x': 2340, 'y': -1850, 'profit': 9.6}, {'id': 34, 'x': -30, 'y': -330, 'profit': 6.0}, {'id': 35, 'x': 1590, 'y': -1660, 'profit': 3.4}] # NM: 45.44 29.91 [11, 12, 13, 17, 23, 29, 31, 32, 34] & Time: 2 s # MK: 45.27 29.65 [12, 17, 34, 23, 11, 13, 32, 31, 5] & Time: 1 s # BB: Time: > 1 m # ---------- case = 'P4' max_total_time = 45 # minute orders = [{'id': 1, 'x': 2390, 'y': 2260, 'profit': 5.1}, {'id': 2, 'x': 1520, 'y': -1480, 'profit': 3.0}, {'id': 3, 'x': -1110, 'y': -1420, 'profit': 6.6}, {'id': 4, 'x': -660, 'y': -2260, 'profit': 4.0}, {'id': 5, 'x': -1360, 'y': 2000, 'profit': 6.8}, {'id': 6, 'x': 1590, 'y': 490, 'profit': 5.5}, {'id': 7, 'x': -370, 'y': -330, 'profit': 9.4}, {'id': 8, 'x': -1970, 'y': -1480, 'profit': 7.0}, {'id': 9, 'x': -890, 'y': 2260, 'profit': 7.9}, {'id': 10, 'x': 2130, 'y': 290, 'profit': 3.7}, {'id': 11, 'x': -1270, 'y': -1270, 'profit': 6.9}, {'id': 12, 'x': -2280, 'y': -1540, 'profit': 8.0}, {'id': 13, 'x': 1480, 'y': 820, 'profit': 3.2}, {'id': 14, 'x': 880, 'y': -1080, 'profit': 3.7}, {'id': 15, 'x': -2210, 'y': 1550, 'profit': 9.6}, {'id': 16, 'x': 40, 'y': -1570, 'profit': 6.1}, {'id': 17, 'x': 1260, 'y': -320, 'profit': 3.4}, {'id': 18, 'x': 630, 'y': -2000, 'profit': 8.4}, {'id': 19, 'x': -2260, 'y': -2260, 'profit': 6.5}, {'id': 20, 'x': 840, 'y': -160, 'profit': 9.6}, {'id': 21, 'x': 2020, 'y': 1150, 'profit': 8.2}, {'id': 22, 'x': 1980, 'y': 2110, 'profit': 9.5}, {'id': 23, 'x': 2170, 'y': -100, 'profit': 5.4}, {'id': 24, 'x': -2130, 'y': 280, 'profit': 9.2}, {'id': 25, 'x': 520, 'y': 2100, 'profit': 6.5}, {'id': 26, 'x': -1290, 'y': -50, 'profit': 7.4}, {'id': 27, 'x': 1390, 'y': 890, 'profit': 4.4}, {'id': 28, 'x': -1760, 'y': 940, 'profit': 5.2}, {'id': 29, 'x': 1500, 'y': -90, 'profit': 7.2}, {'id': 30, 'x': 640, 'y': -2040, 'profit': 9.5}, {'id': 31, 'x': 2450, 'y': -1860, 'profit': 3.3}, {'id': 32, 'x': -1260, 'y': -2310, 'profit': 9.8}, {'id': 33, 'x': -470, 'y': 1880, 'profit': 7.7}, {'id': 34, 'x': -1920, 'y': -1240, 'profit': 3.4}, {'id': 35, 'x': -1800, 'y': -2420, 'profit': 7.6}, {'id': 36, 'x': -800, 'y': -450, 'profit': 6.6}, {'id': 37, 'x': 1980, 'y': -600, 'profit': 3.3}, {'id': 38, 'x': 1090, 'y': -1140, 'profit': 7.5}, {'id': 39, 'x': 1590, 'y': -1760, 'profit': 8.3}, {'id': 40, 'x': 670, 'y': 760, 'profit': 6.3}] # NM: 45.48 44.64 [7, 16, 20, 26, 29, 33, 36, 38, 40] & Time: 7 s # MK: 44.83 44.74 [7, 20, 36, 40, 26, 29, 38, 30, 14] & Time: 1 s # BB: Time: > 1 m # ---------- case = 'P5' max_total_time = 45 # minute orders = [{'id': 1, 'x': -690, 'y': 1590, 'profit': 7.8}, {'id': 2, 'x': -490, 'y': -1430, 'profit': 7.4}, {'id': 3, 'x': -740, 'y': 2100, 'profit': 3.6}, {'id': 4, 'x': 490, 'y': 1170, 'profit': 4.3}, {'id': 5, 'x': 1310, 'y': -1370, 'profit': 8.4}, {'id': 6, 'x': -1500, 'y': -390, 'profit': 8.2}, {'id': 7, 'x': -2340, 'y': -2290, 'profit': 7.0}, {'id': 8, 'x': 2170, 'y': -810, 'profit': 6.1}, {'id': 9, 'x': 280, 'y': -1690, 'profit': 8.2}, {'id': 10, 'x': -1550, 'y': 1120, 'profit': 5.4}, {'id': 11, 'x': 990, 'y': -340, 'profit': 8.0}, {'id': 12, 'x': -1920, 'y': 1820, 'profit': 7.5}, {'id': 13, 'x': -2090, 'y': -1390, 'profit': 6.8}, {'id': 14, 'x': -1840, 'y': 1930, 'profit': 7.0}, {'id': 15, 'x': -1430, 'y': 880, 'profit': 5.8}, {'id': 16, 'x': -2380, 'y': 2360, 'profit': 7.7}, {'id': 17, 'x': 910, 'y': -240, 'profit': 8.7}, {'id': 18, 'x': -1370, 'y': -1420, 'profit': 6.3}, {'id': 19, 'x': 1820, 'y': 1420, 'profit': 6.4}, {'id': 20, 'x': 1420, 'y': -1460, 'profit': 7.3}, {'id': 21, 'x': -20, 'y': 830, 'profit': 6.3}, {'id': 22, 'x': 1470, 'y': -970, 'profit': 4.9}, {'id': 23, 'x': 1320, 'y': -350, 'profit': 3.9}, {'id': 24, 'x': -260, 'y': 1150, 'profit': 6.7}, {'id': 25, 'x': 1740, 'y': -2260, 'profit': 7.5}, {'id': 26, 'x': -280, 'y': 1660, 'profit': 6.0}, {'id': 27, 'x': 1360, 'y': -2290, 'profit': 5.2}, {'id': 28, 'x': 2260, 'y': -2080, 'profit': 8.0}, {'id': 29, 'x': -1220, 'y': 2380, 'profit': 5.6}, {'id': 30, 'x': -1230, 'y': 2360, 'profit': 7.3}, {'id': 31, 'x': -2320, 'y': -1000, 'profit': 6.9}, {'id': 32, 'x': 370, 'y': -430, 'profit': 5.4}, {'id': 33, 'x': 2230, 'y': -2150, 'profit': 5.6}, {'id': 34, 'x': -1970, 'y': -1400, 'profit': 9.2}, {'id': 35, 'x': -1760, 'y': 1420, 'profit': 4.4}, {'id': 36, 'x': 1930, 'y': 410, 'profit': 5.8}, {'id': 37, 'x': 1350, 'y': 930, 'profit': 7.8}, {'id': 38, 'x': -1070, 'y': 2420, 'profit': 6.5}, {'id': 39, 'x': -1270, 'y': -1810, 'profit': 8.9}, {'id': 40, 'x': -950, 'y': -440, 'profit': 7.6}, {'id': 41, 'x': 730, 'y': -1400, 'profit': 9.9}, {'id': 42, 'x': -590, 'y': -1800, 'profit': 9.0}, {'id': 43, 'x': -2220, 'y': 1900, 'profit': 9.5}, {'id': 44, 'x': -2050, 'y': 60, 'profit': 6.5}, {'id': 45, 'x': -1900, 'y': 420, 'profit': 5.6}] # NM: 48.96 44.67 [6, 9, 11, 17, 21, 32, 40, 41, 42] & Time: 19 s # MK: 48.13 43.14 [32, 17, 11, 21, 40, 41, 6, 2, 9] & Time: 1 s # BB: Time: > 1 m # ----------- case = 'P6' max_total_time = 60 # minute orders = [{'id': 1, 'x': 1250, 'y': 380, 'profit': 9.1}, {'id': 2, 'x': -1650, 'y': 990, 'profit': 6.5}, {'id': 3, 'x': -560, 'y': 1970, 'profit': 4.6}, {'id': 4, 'x': -360, 'y': 2240, 'profit': 8.0}, {'id': 5, 'x': 1300, 'y': -2020, 'profit': 10.0}, {'id': 6, 'x': -1600, 'y': 610, 'profit': 7.9}, {'id': 7, 'x': 110, 'y': -870, 'profit': 9.3}, {'id': 8, 'x': -1810, 'y': 890, 'profit': 7.9}, {'id': 9, 'x': -410, 'y': 1920, 'profit': 7.1}, {'id': 10, 'x': -2340, 'y': -170, 'profit': 5.0}, {'id': 11, 'x': -1230, 'y': -1670, 'profit': 6.7}, {'id': 12, 'x': -1420, 'y': -2200, 'profit': 6.2}, {'id': 13, 'x': 1310, 'y': -530, 'profit': 8.1}, {'id': 14, 'x': -300, 'y': 810, 'profit': 8.9}, {'id': 15, 'x': 1130, 'y': -570, 'profit': 3.6}, {'id': 16, 'x': -340, 'y': -430, 'profit': 4.1}, {'id': 17, 'x': -220, 'y': -2100, 'profit': 4.5}, {'id': 18, 'x': -970, 'y': -270, 'profit': 6.5}, {'id': 19, 'x': -1790, 'y': -2470, 'profit': 7.0}, {'id': 20, 'x': 370, 'y': 990, 'profit': 6.5}, {'id': 21, 'x': 510, 'y': -900, 'profit': 3.9}, {'id': 22, 'x': 750, 'y': -1180, 'profit': 5.4}, {'id': 23, 'x': -2020, 'y': 1250, 'profit': 6.4}, {'id': 24, 'x': -1480, 'y': -1410, 'profit': 6.0}, {'id': 25, 'x': -380, 'y': 180, 'profit': 5.2}, {'id': 26, 'x': -1680, 'y': 90, 'profit': 6.5}, {'id': 27, 'x': 500, 'y': -2470, 'profit': 3.7}, {'id': 28, 'x': -2070, 'y': 1710, 'profit': 8.8}, {'id': 29, 'x': -1330, 'y': 990, 'profit': 7.6}, {'id': 30, 'x': 1190, 'y': -470, 'profit': 4.4}, {'id': 31, 'x': -2040, 'y': 2270, 'profit': 7.7}, {'id': 32, 'x': -1630, 'y': 320, 'profit': 5.6}, {'id': 33, 'x': 1710, 'y': 610, 'profit': 3.9}, {'id': 34, 'x': -2240, 'y': -2000, 'profit': 6.8}, {'id': 35, 'x': -1730, 'y': 740, 'profit': 6.8}, {'id': 36, 'x': 860, 'y': 10, 'profit': 3.8}, {'id': 37, 'x': 960, 'y': 1640, 'profit': 4.1}, {'id': 38, 'x': -1960, 'y': -1280, 'profit': 7.9}, {'id': 39, 'x': 1300, 'y': 100, 'profit': 3.6}, {'id': 40, 'x': -1370, 'y': -1180, 'profit': 8.6}, {'id': 41, 'x': -1110, 'y': 2360, 'profit': 8.5}, {'id': 42, 'x': -320, 'y': 1070, 'profit': 8.6}, {'id': 43, 'x': 2000, 'y': 1080, 'profit': 6.7}, {'id': 44, 'x': 1040, 'y': -2230, 'profit': 8.3}, {'id': 45, 'x': 220, 'y': 2000, 'profit': 8.0}, {'id': 46, 'x': -1920, 'y': 1220, 'profit': 7.5}, {'id': 47, 'x': 990, 'y': -1470, 'profit': 4.9}, {'id': 48, 'x': -800, 'y': 130, 'profit': 7.1}, {'id': 49, 'x': -210, 'y': 1020, 'profit': 7.8}, {'id': 50, 'x': 1620, 'y': -1020, 'profit': 3.3}, {'id': 51, 'x': -2240, 'y': 690, 'profit': 8.7}, {'id': 52, 'x': -120, 'y': 2430, 'profit': 3.3}, {'id': 53, 'x': -1960, 'y': -220, 'profit': 6.5}, {'id': 54, 'x': 1890, 'y': 670, 'profit': 4.4}, {'id': 55, 'x': -60, 'y': -2150, 'profit': 8.8}, {'id': 56, 'x': 2270, 'y': 250, 'profit': 4.6}, {'id': 57, 'x': -2420, 'y': -1060, 'profit': 4.6}, {'id': 58, 'x': 1560, 'y': 2330, 'profit': 8.6}, {'id': 59, 'x': -420, 'y': 600, 'profit': 5.3}, {'id': 60, 'x': 1370, 'y': 1820, 'profit': 9.4}, {'id': 61, 'x': -1250, 'y': 2360, 'profit': 3.9}, {'id': 62, 'x': -1840, 'y': -1390, 'profit': 3.1}, {'id': 63, 'x': -660, 'y': -1760, 'profit': 7.4}, {'id': 64, 'x': -1020, 'y': 1510, 'profit': 4.6}, {'id': 65, 'x': -2270, 'y': -2380, 'profit': 7.9}, {'id': 66, 'x': -2250, 'y': 220, 'profit': 5.6}, {'id': 67, 'x': -30, 'y': -2010, 'profit': 3.3}, {'id': 68, 'x': -2010, 'y': 1780, 'profit': 8.9}, {'id': 69, 'x': 0, 'y': 1910, 'profit': 8.0}, {'id': 70, 'x': 190, 'y': -2310, 'profit': 9.9}, {'id': 71, 'x': -220, 'y': 2300, 'profit': 9.4}, {'id': 72, 'x': -2250, 'y': 2200, 'profit': 5.7}, {'id': 73, 'x': 1500, 'y': 1160, 'profit': 9.4}, {'id': 74, 'x': 2370, 'y': 1510, 'profit': 3.8}, {'id': 75, 'x': -1290, 'y': 650, 'profit': 7.3}, {'id': 76, 'x': -840, 'y': 1740, 'profit': 8.2}, {'id': 77, 'x': -1490, 'y': -1920, 'profit': 9.7}, {'id': 78, 'x': 1020, 'y': -430, 'profit': 9.2}, {'id': 79, 'x': 370, 'y': 170, 'profit': 9.9}, {'id': 80, 'x': 1860, 'y': 2130, 'profit': 8.9}, {'id': 81, 'x': -2070, 'y': 100, 'profit': 3.3}, {'id': 82, 'x': -410, 'y': -970, 'profit': 7.0}, {'id': 83, 'x': 1880, 'y': -850, 'profit': 5.6}, {'id': 84, 'x': -1260, 'y': -520, 'profit': 4.0}, {'id': 85, 'x': -1890, 'y': -2040, 'profit': 7.2}, {'id': 86, 'x': 960, 'y': 1950, 'profit': 3.5}, {'id': 87, 'x': -170, 'y': 1960, 'profit': 8.1}, {'id': 88, 'x': 1120, 'y': -2020, 'profit': 6.0}, {'id': 89, 'x': -1700, 'y': -1440, 'profit': 6.0}, {'id': 90, 'x': -670, 'y': -1440, 'profit': 5.5}, {'id': 91, 'x': -2440, 'y': 1940, 'profit': 8.1}, {'id': 92, 'x': 1820, 'y': 110, 'profit': 9.9}, {'id': 93, 'x': 1130, 'y': -940, 'profit': 5.5}, {'id': 94, 'x': -1790, 'y': 1580, 'profit': 4.7}, {'id': 95, 'x': -350, 'y': -240, 'profit': 9.1}, {'id': 96, 'x': 1160, 'y': 690, 'profit': 7.7}, {'id': 97, 'x': -1740, 'y': -1750, 'profit': 8.5}, {'id': 98, 'x': -1340, 'y': -950, 'profit': 4.4}, {'id': 99, 'x': 940, 'y': 460, 'profit': 6.6}, {'id': 100, 'x': 2130, 'y': -1600, 'profit': 3.3}] # NM: Time: > 1 m # MK: 94.83 58.74 [79, 95, 25, 7, 14, 48, 78, 42, 49, 59, 1, 82, 18, 99, 20, 13] & Time: 1 s # BB: Time: > 1 m # ----------- |
جزییات برنامهها
حل با الگوریتم بازگشتی
این برنامه در ابتدا با گرفتن اطلاعات از کاربر برای هر سفارش، فاصله تا رستوران (رفت و برگشت) را محاسبه می‌کند (masafat) و به کمک آن، زمان (time=masafat/speed) و سود خالص (net_profit=profit-masafat*cast_meter) هر سفارش را جداگانه محاسبه و در لیستی ذخیره می‌کند.
سپس به کمک تابع بازگشتی دو مقدارِ تعداد سفارش‌ها و حداکثر زمان را به عنوان ورودی دریافت و مقدار سود، زمان تحویل و لیست کالاهای پذیرفته شده را به عنوان خروجی نشان می‌دهد.
اگر یکی از دو مقدار ورودی صفر باشد، حداکثر سود خالص و زمان تحویل را برابر صفر و لیست سفارش‌های پذیرفته شده را خالی می‌گذارد. در غیر این صورت اگر زمان سفارش آخر از حداکثر زمان (max_total_time) بیشتر بود، به صورت تابع بازگشتی حداکثر سود خالص و زمان این حالت را برابر حالتی که تعداد n-1 کالا را باید حداکثر در همین زمان برساند قرار می‌دهد. و در غیر این صورت حداکثر سود خالص را برابر بیشترین مقدار بین وقتی که کالای آخر را بردارد (تعداد n-1 کالا را در حداکثر زمان منهای زمان کالا آخر بردارد) یا بر ندارد (تعداد n-1 کالا را حداکثر در همین زمان بردارد) قرار می‌دهد. اگر حالت اینکه کالای آخر را بردارد بزرگتر بود، آن را به لیست پذیرفته شده اضافه می‌کند و زمان و سود خالص آن را نیز به زمان تحویل و حداکثر سود خالص اضافه می‌کند.
حل با الگوریتم حریصانه
جزئیات کامل این برنامه را میتونی در این اسلایدهای تصویری ببینی. به طور خلاصه:
- با قانون فیثاغورث فاصله مبدأ تا مقصد را بدست آورده و آن را در دو ضرب میکنیم زیرا ربات باید هم فاصله را برود و هم باز گردد.
- فاصله بدست آمده را در 0.001 ضرب میکنیم زیرا هر 1 متر که ربات می‌رود 0.001 هزینه دارد.
- فاصله را بر 500 تقسیم میکنیم تا زمان رفتن ربات بر ثانیه بدست آید.
- هزینه – پولی که کاربر می‌دهد = سود
- سود را بر زمان تقسیم کرده تا بفهمیم ربات در هر ثانیه چقدر سود می‌کند .
- برای همه مشتریان این کار را کرده و آن ها را ذخیره میکنیم. (می‌توان برای ذخیره هر یک از dict استفاده کرد.)
- آنها را بر حسب مرحله ۵ مرتب میکنیم. ( sorted(orders1,key=lambda k: k[‘p/t’],reverse=True) )
- داده‌های قبلی را از اول پیمایش کرده اگر سود آن ها منفی نبود و همچنین زمان آن مناسب بود (یعنی هنوز انرژی برای رفتن آن مسافت داشته باشیم) سود و زمان و id آن را در متغیرهایی ذخیره کرده و همینطور تا آخر پیش می‌رویم (هر کدام را ذخیره میکنیم) .
- حال یکبار دیگر از اول پیمایش کرده و هر بار یکی از آن ها را حساب نمی‌کنیم و آنها را در متغیر هایی ذخیره میکنیم (مثلا خانه یکم را حساب نمی‌کنیم و با توجه به شروط مرحله ی ۸ سود آنها را جمع میکنیم بعد که تا آخر حساب کردیم خانه ی ۲ را حساب نمی‌کنیم).
- بیشترین سود را محاسبه کرده و آن را نمایش می‌دهیم.