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

حل مسأله کوله پشتی کسری:

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

ورودی های این مسأله عبارتند از :

• values که یک آرایه از نوع اعشاری می باشد و شامل ارزش هر کدام از اشیا است.
• weights نیز یک آرایه از نوع اعشاری است و شامل وزن هر کدام از اشیا است.
• maxweight  از نوع اعشاری که حداکثر ظرفیت کوله پشتی را نشان می دهد.

متغیرهای الگوریتم عبارتند از:

• strout از نوع رشته ای و به عنوان خروجی تابع در نظر گرفته می شود.
• sum از نوع اعشاری که مجموع ارزش اشیائ قرار داده شده در کوله پشتی را در خود نگه می دارد.
• ratio یک آرایه از نوع اعشاری که نسبت ارزش به وزن هر شی را اندیس معادل آن نگه می دارد.
• pickedItems یک آرایه از نوع اعشاری که مشخص می کند کدام آیتم ها و به چه اندازه ای انتخاب شده اند.  
• 0 یعنی آن اندیس انتخاب نشده است.
• 1 یعنی آیتم آن اندیس بطور کامل انتخاب شده است
• سایر اندازه های بین صفر تا یک نیز یعنی آن مقدار از آیتم انتخاب شده است به طور مثال 0.8 یعنی 80% از آن آیتم انتخاب شده است.

• wtemp یک متغیر از نوع اعشاری است که حاصل جمع اشیای انتخاب شده را نگه می دارد و کوچکتر یا مساوی maxweight است تا زمانیکه با آن برابر شود.
• ic یک متغیر از نوع عدد صحیح که به عنوان شمارنده استفاده می شود.
• best هم یک متغیر از نوع عدد صحیح است که در هر مرحله اندیس بهترین انتخاب را در آن قرار می دهیم.

private string RunKnapsack(values as array of double, weights as array of double, maxweight as double)

strout as string <-- string.Empty;

sum as double <-- 0.0

ratio as array of double <-- new array of double[Length of values]

pickedItems as array of double <-- new array of double [Length of values]

wtemp as double <-- 0.0

ic as integer <-- 0

best as integer <-- 0

if Length of values <> Length of weights then 

show messageBox "Invalid input"

return strout

ic <-- 0

while ic < Length of values do

ratio[ic] <-- values[ic] / weights[ic]

pickedItems[ic] <-- 0

ic <-- ic + 1

while wtemp < maxweight do

best <-- 0

ic <-- 0

while ic < Length of values do

if (pickedItems[ic] == 0) and (ratio[best] < ratio[ic]) then

best <-- ic

ic <-- ic + 1

if (wtemp + weight[best]) <= maxweight then

strout.AppendNewLine("W(" + ToString(best) + ") and P("

+ ToString(best) + ") Has been picked completely")

sum <-- sum + values[best]

wtemp <-- wtemp + weights[best]

pickedItems[best] <-- 1

ratio[best] <-- -1

else

pickedItems[best] <-- values[best] * (maxweight - wtemp) / weights[best]

strout.AppendNewLine("W(" + ToString(best) + ") and P(" + ToString(best) + 

") Has been picked with %" + ToString(pickedItems[best] / values[best] * 100)

sum <-- sum + values[best] * (maxweight - wtemp) /weights[best]

wtemp <-- maxweight

strout <-- "Sum of picked values = " + ToString(sum) + NewLine + strout

شرح الگوریتم :

strout as string <-- string.Empty;

sum as double <-- 0.0

ratio as array of double <-- new array of double[Length of values]

pickedItems as array of double <-- new array of double [Length of values]

wtemp as double <-- 0.0

ic as integer <-- 0

best as integer <-- 0

strout را از نوع رشته ای تعریف کرده و یک رشته ی خالی به نسبت می دهد.

sum را از نوع اعشاری تعریف کرده و مقدار صفر را به آن نسبت می دهد.

ratio  را از نوع آرایه ای از اعداد اعشاری تعریف کرده و یک آرایه از نوع اعداد اعشاری با تعداد اعضای معادل طول پارامتر values به آن نسبت می دهد.

pickedItems نیز دقیقا مانند ratio تعریف می شود.

wtemp یک متغیر از نوع اعشاری است و مقدار اولیه صفر را به آن نسبت می دهیم.

ic و best نیز هر کدام یک متغیر از نوع عدد صحیح هستند و مقدار اولیه صفر به هرکدام نسبت می دهیم که البته در ابتدا می توانیم هیچ مقداری به آنها نسبت ندهیم.

if Length of values <> Length of weights then 

show messageBox "Invalid input"

return strout

اگر طول آرایه values با طول آرایه weights برابر نبود آنگاه یک پیغام نشان داده شود که ورودی اشتباه است و strout که در اینجا یک متن خالی است را به عنوان خروجی تابع برگرداند. عدم برابری طول دو آرایه مذکور به معنی این است که برای یک یا چند شئ وزن تعریف کردیم ولی برایش ارزش تعریف نکرده ایم یا بر عکس. و این یعنی وزن ها ممکن است معادل ارزش هم ردیف خود در آرایه دیگر نباشند.

ic <-- 0

while ic < Length of values do

ratio[ic] <-- values[ic] / weights[ic]

pickedItems[ic] <-- 0

ic <-- ic + 1

در اینجا حتما باید به متغیر ic مقدار صفر دهیم چون در حلقه بعدی به عنوان شمارنده ی حلقه از ابتدای آرایه مورد استفاده بگیرد.

تا زمانیکه ic کوچکتر از طول آرایه values است انجام بده:

خانه ی شماره ic را از آرایه values تقسیم بر خانه ی معادل خود در آرایه weights کن و حاصل را درون خانه ی شماره ic از آرایه ratio قرار بده.

مقدار 0 را به خانه شماره ic از آرایه pickedItems نسبت بده.

یک واحد به شمارنده حلقه اضافه کن.

while wtemp < maxweight do

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

best <-- 0

ic <-- 0

while ic < Length of values do

تا زمانیکه مقدار ic کمتر از طول آرایه values است دستورات زیر را انجام بده:

if (pickedItems[ic] == 0) and (ratio[best] < ratio[ic]) then

اگر خانه شماره ic از عناصر انتخاب شده (یعنی آرایه pickedItems) برابر 0 بود و همچنین مقدار درون خانه ی best از آرایه ratio که شامل نسبت های ارزش به وزن اشیا است کمتر از مقدار درون خانه ic از همین آرایه بود دستور زیر را انجام بده

best <-- ic

ic را درون best بریز.

ic <-- ic + 1

if (wtemp + weight[best]) <= maxweight then

اگر حاصل جمع وزن اشیای انتخاب شده از قبل و وزن شی انتخاب شده ی فعلی کوچکتر یا مساوی وزن قابل تحمل توسط کوله باشد دستورات زیر را انجام بده.

strout.AppendNewLine("W(" + ToString(best) + ") and P("

+ ToString(best) + ") Has been picked completely")

یک خط جدید به strout اضافه کن و بنویس که شی انتخاب شده و با وزن و ارزش آن بطور کامل انتخاب شده است.

sum <-- sum + values[best]

مقدار عددی درون خانه ی best از آرایه values را که حاوی ارزش شی انتخاب شده است با متغیر sum جمع کن و حاصل را مجدد درون متغیر sum بریز.

wtemp <-- wtemp + weights[best]

وزن شی انتخاب شده را با وزن موقت جمع بزن و حاصل را درمتغیر مربوط به وزن موقت قرار بده.

pickedItems[best] <-- 1

در آرایه pickedItems مقدار درون خانه ی best را برابر 1 قرار بده ( این کار یعنی این شی انتخاب شده و در دفعات بعدی مورد انتخاب قرار نمی گیرد).

ratio[best] <-- -1

else

pickedItems[best] <-- values[best] * (maxweight - wtemp) / weights[best]

 (maxweight - wtemp) / weights[best] یعنی به نسبت وزن قابل تحمل باقیمانده از کوله پشتی از شی مورد نظر بردارد و آن را در ارزش آن شی ضرب کند و حاصل را درون خانه best از آرایه pickedItems بریزد. بدین ترتیب در آخرین مرحله اگر وزن قابل تحمل باقیمانده از کوله برابر 3 کیلوگرم باشد و وزن شی انتخاب شده برابر 10 کیلوگرم باشدمقدار 0.3 در مقدار خانه ی best از آرایه values ضرب می شود یعنی 30 درصد از ارزش کل شی برداشته می شود.

strout.AppendNewLine("W(" + ToString(best) + ") and P(" + ToString(best) + 

") Has been picked with %" + ToString(pickedItems[best] / values[best] * 100)

به strout یک خط جدید اضافه کن و درون آن بنویس که شی انتخاب شده دارای چه وزن و ارزشی بود و چند درصد از آن انتخاب شد.

sum <-- sum + values[best] * (maxweight - wtemp) /weights[best]

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

wtemp <-- maxweight

این دستور آخر بخاطر این است که شرط حلقه ی تکرار درست شود و مشخص شود که مقدار برداشته شده دقیقا برابر با مقدار قابل تحمل توسط کوله پشتی است.

در انتها نیز متغیر strout را به عنوان خروجی و گزارش تهیه شده توسط تابع به خروجی منتقل می کنیم.