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

Ուսապարկի խնդրի օրինակ․ անհրաժեշտ է 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), յուրաքանչյուրից իրից տրված քանակից ոչ ավելի։