سوال 46

حل تشریحی سوال شماره 46 دروس مشترک

کنکور ارشد مهندسی فناوری اطلاعات (IT) 1399

46.

فرض کنید یک کوله‌پشتی با ظرفیت 100 داریم. تعدادی شی با حجم و ارزش صحیح داده شده است. می‌خواهیم تعدادی از این اشیاء را در کوله بگذاریم، طوری که اولا در کوله جا شوند و ثانیا مجموع ارزش‌شان بیشینه شود. الگوریتم حریصانه زیر را در نظر بگیرید.

اشیاء را به‌صورت صعودی براساس ارزش روی حجم مرتب می‌کنیم. اشیاء را به‌ترتیب لیست فوق مورد بررسی قرار داده و اگر فضای خالی کوله‌پشتی حداقل به اندازه شی مورد بررسی آن شی را در کوله قرار می‌دهیم.

به ازای کدام ورودی زیر الگوریتم حریصانه جواب بهینه برنمی‌گرداند؟ (در زیر حجم و ارزش اشیاء به‌ترتیب در آرایه‌های V و W آمده است. یعنی شی iام دارای حجم V[i] و ارزش w[i] است.)

$W [1..5] = [3, 1, 1, 1, 1], V [1..5] = [76, 25, 25, 25, 25]$

$W [1..5] = [20, 5, 9, 10, 1], V [1..5] = [70, 30, 45, 25, 40]$

$W [1..5] = [80, 20, 22, 21, 20], V [1..5] = [76, 25, 25, 25, 25]$

همه موارد فوق

پاسخ ها

0 پاسخ

تا کنون پاسخی برای این سوال وارد نشده است،

حل تشریحی سوال شماره 46 دروس مشترک

کنکور ارشد مهندسی فناوری اطلاعات (IT) 1399

پاسخ ها

ارسال پاسخ