Ուսապարկի խնդիր

Ուսապարկի խնդրի օրինակ․ անհրաժեշտ է 15 կգ տարողությամբ ուսապարկում տեղավորել արկղեր այնպես, որ ընդհանուր արժեքականությունը լինի առավելագույնը

Ուսապարկի խնդիրը կոմբինատոր օպտիմիզացման NP-խնդիրներից է։ Խնդիրը իրենից ներկայացնում է սահմանափակ տարողությամբ ուսապարկում, որում պետք է տեղավորել մաքսիմալ թանկարժեք իրեր։ Հենց այդտեղից է ստացել անվանումը։ Ուսապարկի խնդրի տարբեր տարբերակների հետ կարելի է հանդիպել այլ բնագավառներում՝ տնտեսագիտությունում, կիրառական մաթեմատիկայում, կրիպտոգրաֆիայում, գենետիկայում և լոգիստիկայում։

Ընդհանուր առմամբ խնդիրը իր դասական տարբերակում կարելի է ձևակերպել այսպես․ տրված բազմությամբ առարկաներով,որոնք ունեն քաշ և արժեք պետք է ընտրել ամենամեծ արժեքականությամբ ենթաբազմությունը, որը չի գերազանցում ընդհանուր քաշը։

Խնդրի դասական ձևակերպումը

Ենթադրենք ունենք իրերի հավաքածու, որից յուրաքանչյուրը ունի երկու պարամետր՝ քաշ և արժեք։ Ունենք նույնպես ուսապարկ սահմանափակ տարողությամբ։ Խնդիրն այն է, որ պետք է ուսապարկը հավաքել մաքսիմալ արժեքավոր իրերով և հետևել քաշային սահմանափակմանը։

Մաթեմատիկորեն խնդիրը կարելի է ձևակերպել այսպես․ ունենք $n$ բեռ։ Յուրաքանչյուր i-րդ բեռի համար սահմանված է քաշ $w_{i}>0$ և արժեք $v_{i}>0$, $i=1,2,...,n$։ Տրված է W տարողություն։ Պետք է ընտրել բեռերի ենթաբազմություն, որ նրանց քաշը չգերազանցի W քաշը և գումարային արժեքականությունը լինի առավելագույնը։

Ուսապարկի խնդրի այլ տարբերակներ

Գոյություն ունի խնդրի շատ տարբերակներ։ Տարբերվում են միայն ուսապարկի, իրերի և ընտրությունների պայմաններով։

1. 0-1 ուսապարկի խնդիրը (անգլ.՝ 0-1 Knapsack Problem), յուրաքանչյուրից իրից մեկից ոչ ավելի։
2. Սահմանափակված ուսապարկի խնդիր (անգլ.՝ Bounded Knapsack Problem), յուրաքանչյուրից իրից տրված քանակից ոչ ավելի։
3. Անսահմանափակ ուսապարկի խնդիր (ամբողջ թվանի ուսապարկ) (անգլ.՝ Unbounded Knapsack Problem (integer knapsack)), յուրաքանչյուր առարկայից կամայական քանակությամբ։
4. Այլ ընտրություններով ուսապարկի խնդիր (անգլ.՝ Multiple-choice Knapsack Problem).
5. Ուսապարկերի խնդիր (անգլ.՝ Multiple Knapsack Problem), ունենք ուսապարկեր, յուրաքաանչյուրը իր առավելագույն տարողությամբ։ Յուրաքանչյուր առարկան կարելի է դնել ցանկացած ուսապարկում կամ ոչ։
6. Բազամաչափ ուսապարկի խնդիր (անգլ.՝ Multy-dimensional knapsack problem): քաշի փոխարեն տրված է ուրիշ այլ ռեսուրսներ (օրինակ՝ քաշ,ծավալ, տեղավորման ժամանակ)։