«Ուսապարկի խնդիր»–ի խմբագրումների տարբերություն
No edit summary |
No edit summary |
||
Տող 8. | Տող 8. | ||
Մաթեմատիկորեն խնդիրը կարելի է ձևակերպել այսպես․ ունենք <math>n</math> բեռ։ Յուրաքանչյուր i-րդ բեռի համար սահմանված է '''քաշ''' <math> w_i>0 </math> և '''արժեք''' <math>v_i>0</math>, <math>i= 1,2,...,n</math>։ Տրված է W տարողություն։ Պետք է ընտրել բեռերի ենթաբազմություն, որ նրանց քաշը չգերազանցի W քաշը և գումարային արժեքականությունը լինի առավելագույնը։{{sfn|Silvano|1990|p=1}} |
Մաթեմատիկորեն խնդիրը կարելի է ձևակերպել այսպես․ ունենք <math>n</math> բեռ։ Յուրաքանչյուր i-րդ բեռի համար սահմանված է '''քաշ''' <math> w_i>0 </math> և '''արժեք''' <math>v_i>0</math>, <math>i= 1,2,...,n</math>։ Տրված է W տարողություն։ Պետք է ընտրել բեռերի ենթաբազմություն, որ նրանց քաշը չգերազանցի W քաշը և գումարային արժեքականությունը լինի առավելագույնը։{{sfn|Silvano|1990|p=1}} |
||
=== Ուսապարկի խնդրի այլ տարբերակներ === |
|||
Գոյություն ունի խնդրի շատ տարբերակներ։ Տարբերվում են միայն ուսապարկի, իրերի և ընտրությունների պայմաններով։ |
|||
== Արտաքին հղումներ == |
== Արտաքին հղումներ == |
||
15:44, 20 Օգոստոսի 2016-ի տարբերակ
Ուսապարկի խնդիրը կոմբինատոր օպտիմիզացման NP-խնդիրներից է։ Խնդիրը իրենից ներկայացնում է սահմանափակ տարողությամբ ուսապարկում, որում պետք է տեղավորել մաքսիմալ թանկարժեք իրեր։ Հենց այդտեղից է ստացել անվանումը։ Ուսապարկի խնդրի տարբեր տարբերակների հետ կարելի է հանդիպել այլ բնագավառներում՝ տնտեսագիտությունում, կիրառական մաթեմատիկայում, կրիպտոգրաֆիայում, գենետիկայում և լոգիստիկայում։
Ընդհանուր առմամբ խնդիրը իր դասական տարբերակում կարելի է ձևակերպել այսպես․ տրված բազմությամբ առարկաներով,որոնք ունեն քաշ և արժեք պետք է ընտրել ամենամեծ արժեքականությամբ ենթաբազմությունը, որը չի գերազանցում ընդհանուր քաշը։
Խնդրի դասական ձևակերպումը
Ենթադրենք ունենք իրերի հավաքածու, որից յուրաքանչյուրը ունի երկու պարամետր՝ քաշ և արժեք։ Ունենք նույնպես ուսապարկ սահմանափակ տարողությամբ։ Խնդիրը կայանում է նրանում, որ պետք է ուսապարկը հավաքել մաքսիմալ արժեքավոր իրերով և հետևել քաշային սահմանափակմանը։
Մաթեմատիկորեն խնդիրը կարելի է ձևակերպել այսպես․ ունենք բեռ։ Յուրաքանչյուր i-րդ բեռի համար սահմանված է քաշ և արժեք , ։ Տրված է W տարողություն։ Պետք է ընտրել բեռերի ենթաբազմություն, որ նրանց քաշը չգերազանցի W քաշը և գումարային արժեքականությունը լինի առավելագույնը։[1]
Ուսապարկի խնդրի այլ տարբերակներ
Գոյություն ունի խնդրի շատ տարբերակներ։ Տարբերվում են միայն ուսապարկի, իրերի և ընտրությունների պայմաններով։
Արտաքին հղումներ
Ծանոթագրություններ
- ↑ Silvano, 1990, էջ 1