«Ուսապարկի խնդիր»–ի խմբագրումների տարբերություն
ավելացվեց Կատեգորիա:Դինամիկ ծրագրավորում ՀոթՔաթ գործիքով |
No edit summary |
||
Տող 4. | Տող 4. | ||
Ընդհանուր առմամբ խնդիրը իր դասական տարբերակում կարելի է ձևակերպել այսպես․ տրված բազմությամբ առարկաներով,որոնք ունեն քաշ և արժեք պետք է ընտրել ամենամեծ արժեքականությամբ ենթաբազմությունը, որը չի գերազանցում ընդհանուր քաշը։ |
Ընդհանուր առմամբ խնդիրը իր դասական տարբերակում կարելի է ձևակերպել այսպես․ տրված բազմությամբ առարկաներով,որոնք ունեն քաշ և արժեք պետք է ընտրել ամենամեծ արժեքականությամբ ենթաբազմությունը, որը չի գերազանցում ընդհանուր քաշը։ |
||
== Խնդրի դասական ձևակերպումը == |
|||
Ենթադրենք ունենք իրերի հավաքածու, որից յուրաքանչյուրը ունի երկու պարամետր՝ քաշ և արժեք։ Ունենք նույնպես ուսապարկ սահմանափակ տարողությամբ։ Խնդիրը կայանում է նրանում, որ պետք է ուսապարկը հավաքել մաքսիմալ արժեքավոր իրերով և հետևել քաշային սահմանափակմանը։ |
|||
Մաթեմատիկորեն խնդիրը կարելի է ձևակերպել այսպես․ ունենք <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}} |
|||
== Արտաքին հղումներ == |
== Արտաքին հղումներ == |
||
== Ծանոթագրություններ == |
|||
{{ծանցանկ}} |
|||
[[Կատեգորիա:Կիրառական մաթեմատիկա]] |
[[Կատեգորիա:Կիրառական մաթեմատիկա]] |
||
[[Կատեգորիա:Դինամիկ ծրագրավորում]] |
[[Կատեգորիա:Դինամիկ ծրագրավորում]] |
14:55, 20 Օգոստոսի 2016-ի տարբերակ
Ուսապարկի խնդիրը կոմբինատոր օպտիմիզացման NP-խնդիրներից է։ Խնդիրը իրենից ներկայացնում է սահմանափակ տարողությամբ ուսապարկում, որում պետք է տեղավորել մաքսիմալ թանկարժեք իրեր։ Հենց այդտեղից է ստացել անվանումը։ Ուսապարկի խնդրի տարբեր տարբերակների հետ կարելի է հանդիպել այլ բնագավառներում՝ տնտեսագիտությունում, կիրառական մաթեմատիկայում, կրիպտոգրաֆիայում, գենետիկայում և լոգիստիկայում։
Ընդհանուր առմամբ խնդիրը իր դասական տարբերակում կարելի է ձևակերպել այսպես․ տրված բազմությամբ առարկաներով,որոնք ունեն քաշ և արժեք պետք է ընտրել ամենամեծ արժեքականությամբ ենթաբազմությունը, որը չի գերազանցում ընդհանուր քաշը։
Խնդրի դասական ձևակերպումը
Ենթադրենք ունենք իրերի հավաքածու, որից յուրաքանչյուրը ունի երկու պարամետր՝ քաշ և արժեք։ Ունենք նույնպես ուսապարկ սահմանափակ տարողությամբ։ Խնդիրը կայանում է նրանում, որ պետք է ուսապարկը հավաքել մաքսիմալ արժեքավոր իրերով և հետևել քաշային սահմանափակմանը։
Մաթեմատիկորեն խնդիրը կարելի է ձևակերպել այսպես․ ունենք բեռ։ Յուրաքանչյուր i-րդ բեռի համար սահմանված է քաշ և արժեք , ։ Տրված է W տարողություն։ Պետք է ընտրել բեռերի ենթաբազմություն, որ նրանց քաշը չգերազանցի W քաշը և գումարային արժեքականությունը լինի առավելագույնը։[1]
Արտաքին հղումներ
Ծանոթագրություններ
- ↑ Silvano, 1990, էջ 1