حل مسئله کوله پشتی (knapsak) در متلب

حل کوله پشتی با روش برنامه نویسی پویا : کد متلب کوله پشتی با برنامه ریزی پویا

در این پست کد متلب حل کوله پشتی با روش برنامه نویسی پویا را برای شما عزیزان قرار داده ایم. این کد در متلب Matlab پیاده سازی شده است و به همراه فایل توضیحات کد می باشد.

شرح مسئله به این صورت است که ما تعدادی اجسام با وزن مشخص و با ارزش مشخص داریم و میخواهیم اشیایی را انتخاب کنیم که دارای بیشترین ارزش باشند.

و محدودیتی که داریم بر روی وزن کل اشیا می باشد زیرا که کوله پشتی تحمل وزن مشخصی را دارد.

در کوله پشتی صفر ویک ، یک شی یا انتخاب میشود یا انتخاب نمی شود.

برای دانلود کد متلب حل کوله پشتی 0 و 1 با روش برنامه نویسی پویا در متلب بر روی دکمه فوق کلیک کنید.

بعد از پرداخت ، لینک دانلود محصول برای شما ایمیل میشود.

محصول شامل : کد متلب برای حل مسئله کوله پشتی با روش برنامه نویسی پویا می باشد که در نرم افزار matlab شبیه سازی شده و اجرا میشود و خروجی بهینه را نمایش میدهد

بعلاوه یک فایل توضیحات خط به خط که در آن کد را بصورت فارسی توضیح داده ایم.

اگر در خصوص این محصول سوالی داشتید، با شماره درج شده در سایت تماس بگیرید.

https://matlab24.ir/knapsack

تعاریف ما برای مسئله کوله پشتی به صورت زیر می باشد:

  • یک بردار وزن به نام W خواهیم داشت که وزن اشیا را در ان وارد میکنیم
  • یک بردار ارزش به نام V خواهیم داشت که ارزش اشیا را در ان وارد میکنیم
  • و همچنین یک متغیر W_total داریم که حداکثر وزن قابل قبول را در ان وارد میکنیم

حال میخواهیم با الگوریتم پویا، اشیایی را انتخاب کنیم که بیشترین ارزش را در مجموع داشته باشند با این شرط که مجموع وزن اشیا کمتر مساوی وزن مجاز کوله پشتی باشد.

مثالی از روش حل کوله پشتی

مثال : برای پر کردن کوله پشتی با وزن قابل تحمل 11 با استفاده از اشیای 4،3،2،1 و 5 که ارزش و وزن آنها در جدول زیر آمده است:

  • وزن 1 2 5 6 7
  • ارزش 1 6 18 22 28

مرحله اول حل کوله پشتی با برنامه نویسی پویا در متلب

به کمک الگوریتم ارائه شده می توانیم فقط دو شی 3و 4 را برداریم که سود بیشینه حاصل برابر است با 40 خواهد شد.
در مرحله اول الگوریتم ماتریس B شبه به شکل زیر پر میشود چون 5 شی داریم و وزن حداکثر 11 می باشد

پس طبق تعریف ماتریس B دارای 6 سطر و 12 ستون می باشد

یعنی ماتریس B شبیه جدول زیر خواهد بود

کوله پشتی با روش برنامه نویسی پویا

مرحله دوم حل کوله پشتی با برنامه نویسی پویا در متلب

در مرحله دوم با استفاده از ماتریس B میخواهیم اشیای انتخاب شده را پیدا کنیم که برای این کار به صورت زیر عمل می کنیم.

از درایه B[6,12] شروع کرده چون مقدار این درایه با مقدار بالایی خود یعنی B[5,12] برابر است

پس ما از شی پنجم درون کوله قرار ندادیم. حال چون مقدار B[5,12] با B[4,12] برابر نیست پس حتما از شی چهارم استفاده شده است.

ظرفیت باقی مانده کوله برابر 5 = 6-11 می باشد.

حال کار را با درایه B[5,6] ادامه می دهیم و همین روال را تکرار میکنیم تا زمانی که ظرفیت باقی مانده کوله یعنی j بزرگتر از صفر باشد و اشیای انتخاب شده برابر با شی 3و4 میشوند
که ما در کد همین روش را منتها با کمک آرایه های S و p انجام دادیم.

برای دانلود کد متلب حل کوله پشتی 0 و 1 با روش برنامه نویسی پویا در متلب بر روی دکمه فوق کلیک کنید.

بعد از پرداخت ، لینک دانلود محصول برای شما ایمیل میشود.

محصول شامل : کد متلب برای حل مسئله کوله پشتی با روش برنامه نویسی پویا می باشد که در نرم افزار matlab شبیه سازی شده و اجرا میشود و خروجی بهینه را نمایش میدهد

بعلاوه یک فایل توضیحات خط به خط که در آن کد را بصورت فارسی توضیح داده ایم.

اگر در خصوص این محصول سوالی داشتید، با شماره درج شده در سایت تماس بگیرید.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *