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

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

• یک بردار وزن به نام 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 انجام دادیم.