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

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

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

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

یک بردار وزن به نام W خواهیم داشت که وزن اشیا را در ان وارد میکنیم
یک بردار ارزش به نام V خواهیم داشت که ارزش اشیا را در ان وارد میکنیم
و همچنین یک متغیر W_total داریم که حداکثر وزن قابل قبول را در ان وارد میکنیم
حال میخواهیم با الگوریتم پویا، اشیایی را انتخاب کنیم که بیشترین ارزش را در مجموع داشته باشند با این شرط که مجموع وزن اشیا کمتر مساوی وزن مجاز کوله پشتی باشد.

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

مثال : برای پر کردن کوله پشتی با وزن قابل تحمل ۱۱ با استفاده از اشیای ۴،۳،۲،۱ و ۵ که ارزش و وزن آنها در جدول زیر آمده است
وزن ۱ ۲ ۵ ۶ ۷
ارزش ۱ ۶ ۱۸ ۲۲ ۲۸

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

به کمک الگوریتم ارائه شده می توانیم فقط دو شی ۳و ۴ را برداریم که سود بیشینه حاصل برابر است با ۴۰ خواهد شد.
در مرحله اول الگوریتم ماتریس B شبه به شکل زیر پر میشود چون ۵ شی داریم و وزن حداکثر ۱۱ می باشد پس طبق تعریف ماتریس B دارای ۶ سطر و ۱۲ ستون می باشد

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

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

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

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

از درایه B[6,12] شروع کرده چون مقدار این درایه با مقدار بالایی خود یعنی B[5,12] برابر است پس ما از شی پنجم درون کوله قرار ندادیم. حال چون مقدار B[5,12] با B[4,12] برابر نیست پس حتما از شی چهارم استفاده شده است.
ظرفیت باقی مانده کوله برابر ۵ = ۶-۱۱ می باشد. حال کار را با درایه B[5,6] ادامه می دهیم و همین روال را تکرار میکنیم تا زمانی که ظرفیت باقی مانده کوله یعنی j بزرگتر از صفر باشد و اشیای انتخاب شده برابر با شی ۳و۴ میشوند
که ما در کد همین روش را منتها با کمک آرایه های S و p انجام دادیم.

 

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

کليک جهت خريد کالا ، به منظور پذيرش قوانين و مقررات سايت مي باشد .

نظر خود را اینجا بنویسید!

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