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

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

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

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

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

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

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