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

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

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

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

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

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

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

توابع محاسبه ب.م.م (GCD) و ک.م.م (LCM) دو عدد به زبان های مختلف

توابع محاسبه ب.م.م (GCD) و ک.م.م (LCM) دو عدد به زبان های مختلف : 

F#: 

let GCD(a : int, b : int) : int = 

    let mutable rv : int = 0

    let mutable ia : int = a

    let mutable ib : int = b

    while rv = 0 do

        if ia = 0 then

            rv <- ib

        else

            ib <- ib % ia

        if ib = 0 then

            rv <- ia

        else

            ia <- ia % ib

    rv 

   

بدست آوردن کوچکترین مضرب مشترک (ک.م.م) و بزرگترین مقسوم علیه مشترک (ب.م.م) دو یا چند عدد.

به منظور محاسبه کوچکترین مضرب مشترک و بزرگترین مقسوم علیه مشترک دو عدد می بایست اعمال زیر را انحام دهیم : 

1 -  برای ب.م.م (GCD) دو عدد مانند a و b:

1. شروع
2. اگر a=0 
3. b را برگردان
4. حاصل تقسیم صحیح b بر a را درون b قرار بده
5. اگر b=0 آنگاه
6. a را برگردان
7. حاصل تقسیم صحیح a بر b را درون a قرار بده
8. برو به مرحله 2