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

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

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

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

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

Ուսապարկի խնդրի այլ տարբերակներ 
Գոյություն ունի խնդրի շատ տարբերակներ։ Տարբերվում են միայն ուսապարկի, իրերի և ընտրությունների պայմաններով։
 0-1 ուսապարկի խնդիրը (), յուրաքանչյուրից իրից մեկից ոչ ավելի։
 Սահմանափակված ուսապարկի խնդիր (), յուրաքանչյուրից իրից տրված քանակից ոչ ավելի։
 Անսահմանափակ ուսապարկի խնդիր (ամբողջ թվանի ուսապարկ) (), յուրաքանչյուր առարկայից կամայական քանակությամբ։
 Այլ ընտրություններով ուսապարկի խնդիր ().
 Ուսապարկերի խնդիր (), ունենք ուսապարկեր, յուրաքաանչյուրը իր առավելագույն տարողությամբ։ Յուրաքանչյուր առարկան կարելի է դնել ցանկացած ուսապարկում կամ ոչ։
 Բազամաչափ ուսապարկի խնդիր (): քաշի փոխարեն տրված է ուրիշ այլ ռեսուրսներ (օրինակ՝ քաշ,ծավալ, տեղավորման ժամանակ)։

Արտաքին հղումներ

Ծանոթագրություններ 

Կիրառական մաթեմատիկա
Դինամիկ ծրագրավորում