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

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

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

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

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

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

Մաթեմատիկորեն խնդիրը կարելի է ձևակերպել այսպես․ ունենք $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), յուրաքանչյուրից իրից տրված քանակից ոչ ավելի։
3. Անսահմանափակ ուսապարկի խնդիր (ամբողջ թվանի ուսապարկ) (անգլ.՝ Unbounded Knapsack Problem (integer knapsack)), յուրաքանչյուր առարկայից կամայական քանակությամբ։
4. Այլ ընտրություններով ուսապարկի խնդիր (անգլ.՝ Multiple-choice Knapsack Problem)։
5. Ուսապարկերի խնդիր (անգլ.՝ Multiple Knapsack Problem), ունենք ուսապարկեր, յուրաքաանչյուրը իր առավելագույն տարողությամբ։ Յուրաքանչյուր առարկան կարելի է դնել ցանկացած ուսապարկում կամ ոչ։
6. Բազամաչափ ուսապարկի խնդիր (անգլ.՝ Multy-dimensional knapsack problem): քաշի փոխարեն տրված է ուրիշ այլ ռեսուրսներ (օրինակ՝ քաշ,ծավալ, տեղավորման ժամանակ)։

Литература

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

1. (not translated to en) Алгоритмы. Введение в разработку и анализ — Moscow: (untranslated), 2006. — P. 160—163. — 576 p. — ISBN 978-5-8459-0987-9</includeonly
2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-ое. — М.: «Вильямс», 2006. — С. 456—458. — ISBN 0-07-013151-1
3. Роберт Седжвик Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. — 3-е. — Россия, Санкт-Петербург: «ДиаСофт», 2002. — С. 688. — ISBN 5-93772-047-4, 0-201-35088-2
4. Burkov V., (not translated to en), (not translated to en) Прикладные задачи теории графов / A. Gorgidze — Tbilisi: Вычислительный центр АН СССР, 1974. — 231 p.</includeonly
5. В. Н. Бурков, Д. А. Новиков. Элементы теории графов. — 2001. — С. 28.
6. С. Окулов. Программирование в алгоритмах. — 1-е. — Бином. Лаборатория знаний, 2007. — С. 384. — ISBN 5-94774-010-9
7. Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms, and Source Code in C. — 2-ое. — Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
8. А. Саломаа. Криптография с открытым ключом = Public-Key Cryptography. — М.: Мир, 1995. — С. 102—150. — ISBN 5–03–001991–X
9. Н. Коблиц. Курс теории чисел в криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 254. — ISBN 5-85484-014-6
10. Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации (ռուս.): учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9</includeonly
11. Осипян В. О. О системе защиты информации на основе проблемы рюкзака // Известия Томского политехнического университета [Известия ТПУ]. — 2006. — Т. 309. — № 2. — С. 209—212.

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

1. Silvano Martelo, Paolo Toth Knapsack problems. — Great Britain: Wiley, 1990. — 306 с. — ISBN 0-471-92420-2
2. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems — Springer Science+Business Media, 2004. — 548 p. — ISBN 978-3-642-07311-3 — doi:10.1007/978-3-540-24777-7</includeonly
3. K. Riedhammer, D. Gillick, B. Favre, and D. Hakkani-Tür Packing the Meeting Summarization Knapsack. — Brisbane Australia: Proc. Interspeech, Brisbane, Australia, 2008.
4. Bretthauer K. M., Shetty B. The nonlinear knapsack problem – algorithms and applications // European Journal of Operational Research — Elsevier BV, 2002. — Vol. 138, Iss. 3. — P. 459–472. — ISSN 0377-2217; 1872-6860 — doi:10.1016/S0377-2217(01)00179-5</includeonly

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

• Welcome to the Knapsack(անգլ.)
• Knapsack Problem By Eric Grimsom John Guttag — MIT(անգլ.)
• Knapsack Problem solutions in many languages(անգլ.)
• Das Rucksack-Problem (Knapsack Problem)(գերմ.)