Dinamik programmalash

1. Oldin muzxonaga birinchi xil xomashyolarni joylashtiramiz. Joylashtirilgan yuklarning qiymatini f1 (W ) deb belgilasak, u holda

• 1. Oldin muzxonaga birinchi xil xomashyolarni joylashtiramiz. Joylashtirilgan yuklarning qiymatini f1 (W ) deb belgilasak, u holda

f1 (W) = max {Xi W}

ning qiymati quyidagi

• X1P1 ≤ W;
• X1 = 0,1,2,3….

shartlar bajarilganda topish kerak bo'ladi. Bu yerda tengsizlikdan

bo‘lgani uchun kelib chiqadi.

Bu funksiyaning grafigi 1-chizmada ko‘rsatilgan. Shunday qilib, muzxona birinchi xil xomashyo bilan to‘ldirilganda f1 (W) uning qiymatini topdik. Endi muzxonaga x1 va x2 xil xomashyolar joylashtirilganda f2 (W) ning maksimum qiymatini topaylik. Agar ikkinchi xil xomashyodan x2 dona joylashtirilgan bo‘lsa, u holda muzxonaning hajmini hisobga olsak, birinchi xil xomashyodan W — X2 P2 tonna olish mumkin va uning qiymati f1 (W — X2 P2 ) so'mga teng bo‘ladi. Umumiy qiymat esa X2 V2 + f1(W — X2P2 ) ga teng bo‘ladi. Bularga asoslanib faqat x2 ning qiymatini topsak bas. Shunday qilib, muzxonaga joylashtirilgan birinchi va ikkinchi xil xomashyolarning maksimum qiymati quyidagicha bo'ladi:

• Bu funksiyaning grafigi 1-chizmada ko‘rsatilgan. Shunday qilib, muzxona birinchi xil xomashyo bilan to‘ldirilganda f1 (W) uning qiymatini topdik. Endi muzxonaga x1 va x2 xil xomashyolar joylashtirilganda f2 (W) ning maksimum qiymatini topaylik. Agar ikkinchi xil xomashyodan x2 dona joylashtirilgan bo‘lsa, u holda muzxonaning hajmini hisobga olsak, birinchi xil xomashyodan W — X2 P2 tonna olish mumkin va uning qiymati f1 (W — X2 P2 ) so'mga teng bo‘ladi. Umumiy qiymat esa X2 V2 + f1(W — X2P2 ) ga teng bo‘ladi. Bularga asoslanib faqat x2 ning qiymatini topsak bas. Shunday qilib, muzxonaga joylashtirilgan birinchi va ikkinchi xil xomashyolarning maksimum qiymati quyidagicha bo'ladi: