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

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

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

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

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

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

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

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

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

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

Литература

ռուսերեն լեզվով

1. Կաղապար:Source
2. Կաղապար:Ռուսերեն գիրք
3. Կաղապար:Ռուսերեն գիրք
4. Կաղապար:Source
5. Կաղապար:Ռուսերեն գիրք
6. Կաղապար:Ռուսերեն գիրք
7. Կաղապար:Ռուսերեն գիրք
8. Կաղապար:Ռուսերեն գիրք
9. Կաղապար:Ռուսերեն գիրք
10. Կաղապար:Source
11. Կաղապար:Ռուսերեն հոդված

անգլերեն լեզվով

1. Կաղապար:Ռուսերեն գիրք
2. Կաղապար:Source
3. Կաղապար:Ռուսերեն հոդված
4. Կաղապար:Source

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

• Welcome to the KnapsackԿաղապար:Ref-en
• Knapsack Problem By Eric Grimsom John Guttag — MITԿաղապար:Ref-en
• Knapsack Problem solutions in many languagesԿաղապար:Ref-en
• Das Rucksack-Problem (Knapsack Problem)Կաղապար:Ref-de