سوال 10
حل تشریحی سوال شماره 10 حل مسئله
کنکور دکتری مهندسی فناوری اطلاعات (IT) 1404
10.
فرض کنید یک مجموعه از سکه با ارزشهای دارید. می خواهید این سکه ها را به دو گروه تقسیم کنید به طوری که مجموع ارزشهای سکه ها در دو گروه تا حد ممکن برابر باشد. راه حل بهینه چیست؟
1)
تقسیم سکهها بهصورت تصادفی و بررسی مجموع هر گروه تا زمانی که به یک تقسیمبندی نزدیک بهینه برسید.
2)
مرتبسازی سکهها بر اساس مقدار و سپس اختصاص سکهها به دو گروه بهصورت متناوب (یک سکه به گروه اول و سکه بعدی به گروه دوم)
3)
استفاده از یک روش حریصانه به این صورت که بزرگترین سکه موجود را انتخاب کرده و آن را به گروهی اختصاص دهید که مجموع فعلی کمتری دارد.
4)
استفاده از برنامهریزی پویا برای پیدا کردن نزدیکترین مجموع ممکن به نصف كل مجموع سکهها (این روش با استفاده از یک جدول پویا بررسی میکند که آیا میتوان یک زیر مجموعه با مجموع مشخص ساخت یا خیر)
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،