logo

Ryukzak masalasi

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

152.9228515625 KB
“Ryukzak masalasi ”
MUNDARIJA:
1.Kirish
2.Ryukzak muammosi
3. Hisoblashning murakkabligi
4.Oldindan algoritmni dinamik dasturlash
5.hukmdorlik munosabatlari
6.Kop ob’yektli ryukzak muammosi
6.ko’p o’lchovli ryukzak muammosi
7.Bir nechta ryukzak muammosi
8.Jami ryukzak muammosi
9.XULOSA
10.ADABIYOTLAR Kirish
Bugungi   kunda   ishlatilgan   barcha   narsalar   mamlakat   loyiha   boshqaruvi
usullari   va   modellari   ijrochilar   darajasiga   mo'ljallangan:   loyiha   menejerlari,
boshqaruv jamoasi, barcha zarur resurslar bilan jihozlangan mutaxassislar. Yuqori
darajalar   uchun   iqtisodiyotni   boshqarish-tarmoqlar,   davlat   korporatsiyalari,
xoldinglar   darajasi-loyiha   boshqaruvining   tegishli   modellari   va   usullari   ishlab
chiqilmagan.   Biroq,   bu   strategik   qarorlar   qabul   qilish   darajasi,   50   haqida   unga
bog'liq%   loyiha   faoliyatining   muvaffaqiyati,   barcha   resurslar   unga   qaratilgan   va
eng muhim qarorlar qabul qilinadi. [1, p. 3] bu miqdor qayd etiladi muvaffaqiyatli
loyihalar   uchun   muvaffaqiyatsiz   loyihalar   mamlakatimizda   turli   hisob-kitoblarga
ko'ra,   40   dan   60%   gacha.   Shuning   uchun,   loyiha   boshqarish   qobiliyatsiz   asosiy
sabablaridan biri hisoblanadi,yuqori boshqaruv darajalari kam ishtirok etadi ushbu
faoliyatda   va   zamonaviy   metodologiya   va   loyihani   boshqarish   texnologiyasi
hisobga   olinmaydi   ularning   manfaatlari   etarli   darajada.Xorijda   loyiha   ehtiyoj
ilmiy-tadqiqot va rivojlantirish boshqarish, va, xususan, uning yuqori darajasi uzoq
vaqt davomida amalga oshirilgan. Bu yaratilganidan dalolat beradi va PATTERN
[2]kabi tizimlarning ishlashi, QUEST [3], TORQUE [4], PPB [5], PROFILE [6],
60-yillarning   oxirida   AQShda   yaratilgan.   Ushbu   tizimlarning   barchasi
rejalashtirish   ob'ektining   "maqsad-vazifalar"   daraxti   shaklida   turli   parametrlar,
qiymatlar   bilan   tavsiflanadi   ular   ekspert   baholarini   qayta   ishlash   yo'li   bilan
belgilanadi.   O'ziga   xos   xususiyati   ushbu   kompleks   rejalashtirish   sxemalari   bir
model   sifatida   ishlatiladi   raqamli   qiymatlar   (masalan,   yillik   xarajatlar   mavzu
bo'yicha) va miqdoriy ko'rsatkichlarning ekspert baholashlari. Biroq, bu holat emas
texnikadan   keng   foydalanishga   to'sqinlik   qiladi   ma'lumotlarni   tayyorlash   uchun
belgilangan   sinf   investitsiya   siyosatini   amalga   oshirish   va   yirik   innovatsiyalarni
moliyalashtirish   bo'yicha   yuqori   darajadagi   boshqaruv   qarorlarini   qabul   qilish
loyihalar.
  1978da   mamlakatimizda   bunday   maqsadlar   uchun   analitik   vosita   sifatida
taklif   qilindi   dastur-maqsadli   ierarxik   sxemalar   usuli   ilmiy-tadqiqot   va rivojlantirish rejalashtirish [7]. Ushbu usulning afzalligi ekspert baholarini qo'llash
uchun   yaxshi   mo'ljallangan   qurilma,   qaror   qabul   qiluvchi   shaxs   (LPR)   rejani
belgilaydi, mezonlarni mustaqil ravishda ko'rsatadi va ularga subyektiv bo'lmagan
hisob-kitoblarni   beradi   qabul   qilingan   rejani   ham   tuzatadi.   Ushbu   texnikada
baholash mezonlarining ikkilik tabiati va hal qiluvchi qoidalarning oddiy tuzilishi
LPRNI   belgilangan   maqsadlarga   muvofiq   cheklangan   resurslarni   taqsimlash
vositasini taqdim etadi dastlabki investitsiya siyosatini interaktiv tarzda o'zgartirish
uchun. Biroq, bu sodir bo'ladi tavsiya etilgan yechim olib keladigan holatlar ba'zi
past-ustuvor   loyihalarni   moliyalashtirish   voz   va   o'zgartirish   kerak   tashkil   etilgan
tashkiliy   tuzilma.   Shunday   qilib,   samarali   model   va   algoritmlarni   ishlab   chiqish
zarurati paydo bo'ladi kichik tizim bo'lishi kerak bo'lgan bunday loyiha boshqaruv
tizimining yuqori darajasi uchun qurilma amalga oshiriladigan loyihalar portfelini
tanlash   va   boshqarish.   Ushbu   maqolada   loyihalar   portfelining   maqbul   tanlovi   va
taqsimoti   ko'rib   chiqildi   uni   amalga   oshirish   uchun   resurslar   alohida   vazifa
shaklida optimallashtirish-ryukzak haqida ko'p o'lchovli vazifa. Ryukzak muammosi
Hozirgi vaqtda texnologik va ilmiy taraqqiyotga qaramasdan, NP-to'liq qarorida
orqa   ryukzak   vazifalari,   haqiqiy   hayotdan   olingan   bunday   o'lchamlarning
aksariyatini   hal   qilish   muammo   bo'lib   qolmoqda.   [8   va   9]   asosiy   usullarini
ta'riflaydi, turli vazifa variantlari uchun ishlatiladi
Ryukzak muammosi
1-rasm ryukzak muammosi.
Bir  o'lchovli  ( cheklovli ) ryukzak muammosining  misoli:  umumiy og'irlikni
15   kg   gacha   yoki   unga   teng   ushlab   turganda   pul   miqdorini   maksimal   darajada
oshirish   uchun   qaysi   qutilarni   tanlash   kerak?   A   bir   nechta   cheklangan   muammo
qutilarning vaznini ham, hajmini ham ko'rib chiqishi mumkin. (Qaror: agar har bir
qutining   biron   bir   raqami   mavjud   bo'lsa,   unda   uchta   sariq   quti   va   uchta   kulrang
quti; agar ko'rsatilgan qutilar mavjud bo'lsa, unda yashil qutidan tashqari barchasi.)
Keling,   KS   ()   funktsiyasi   bilan   amalga   oshiriladigan   algoritmga   va   orqa
ryukzak   uchun   ob'ektlarning  ketma-ketligini   shakllantirish   dinamikasiga   qisqacha
to'xtalamiz.   Rekursiya   j   -   tartib   raqami   (noldan   va   undan   keyin)   bilan   tartibga
solinadi (rasmga qarang).8). J chuqurligining har bir chaqiruvida i-element (i, j = 0,
1, ..., m-1) hisobiga qisman yechimni kengaytirishga urinish amalga oshiriladi. Shu
bilan birga, i   parametri   noldan va  undan  keyin birlikka teng  bo'lgan  qadam  bilan
o'zgaradi,   qisman   yechimni   kengaytirish   uchun   ruxsat   etilgan   ob'ektning   eng kichik   sonining   qiymatini   olishga   harakat   qiladi.   Har   qanday   oldingi   recursive
chaqiruviga   o'tishda   i   parametri   joriy   darajadagi   qiymatdan   birlikka   teng   qadam
bilan o'zgarishni davom ettiradi, shuningdek qisman yechimni kengaytirish uchun
ruxsat  etilgan ob'ektning eng kichik raqamini olishga harakat  qiladi. Agar hozirgi
rekursiv chaqiruvda qurilgan qisman qaror endi o'zgartirilmasa, avvalgi chaqiruvga
qaytish bo'ladi. J=0 darajasidan qaytib kelganda, hisob-kitoblar to'xtatiladi, ammo
bu   vaqtga   kelib,   muammoni   hal   qilish   allaqachon   olingan   va   ot   vektorida
joylashgan.
KS() funktsiyasini qo'shimcha parametri bilan ta'minlasangiz va uni takroriy
chaqiruvlarda   quyidagi   tarzda   ishlatsangiz,   hisob-kitoblarning   sezilarli
tezlashishiga   erishish   mumkin.   Ks   ga   dastlabki   murojaat   qilinganda   ()   =   0   ni
hisoblang.   Bundan   tashqari,   agar   qisman   yechimga   ba'zi   rekursiv   chaqiruvlar   i
mavzusiga   kiritilgan   bo'lsa,   keyingi   recursiv   darajaga   o'tishda   sizni   qo'yishingiz
kerak.   Bu   qisman   yechimni   yanada   kengaytirishga   harakat   qilganda,   bu   qiymat
(nol   emas)   va   ob'ektning   boshlang'ich   raqami   sifatida   ishlatiladi.   Shuni   esda
tutingki,   bu   holda   pos   belgilarining   vektori   mutlaqo   keraksiz   bo'lib   qoladi,   unda
ob'ektlarning qisman yechimiga ulangan raqamlar ilgari qayd etilgan.
  Ryukzak   muammosi   kombinatorial   optimallashtirish :   Har   birining   vazni   va
qiymati   bo'lgan   buyumlar   to'plamini   hisobga   olgan   holda,   jami   og'irlik   berilgan
chegaradan   kichik   yoki   unga   teng   bo'lgan   va   umumiy   qiymati   iloji   boricha   katta
bo'lishi   uchun   to'plamga   kiritiladigan   har   bir   narsaning   sonini   aniqlang.   Bu   o'z
nomini   belgilangan   o'lcham   bilan   cheklangan   kishi   duch   keladigan   muammodan
kelib   chiqadi   ryukzak   va   uni   eng   qimmatbaho   buyumlar   bilan   to'ldirishi   kerak.
Muammo   ko'pincha   paydo   bo'ladi   resurslarni   taqsimlash   bu   erda   qaror   qabul
qiluvchilar ajratilgan byudjet yoki vaqt cheklovi bo'yicha bo'linmaydigan loyihalar
yoki vazifalar to'plamini tanlashlari kerak.
1999 yil Stoni Bruk universiteti algoritmi omborini o'rganish natijasida 75 ta
algoritmik   masaladan   ryukzak   muammosi   eng   ommabop   19-o'rin   va   eng   zarur bo'lgan uchinchi o'rinni egallaganligi  ko'rsatildi.   qo ' shimchali   daraxtlar   va   ryukzak
muammosi .
Ryukzakdagi   muammolar   turli   sohalarda   real   hayotda   qaror   qabul   qilish
jarayonida   paydo   bo ' ladi ,   masalan ,   xomashyoni   kesishning   eng   kam
isrofgarchiligini   topish , [4]
  tanlash   investitsiyalar   va   portfellar , [5]
  uchun   aktivlarni
tanlash   aktivlar   bilan   ta ' minlangan   qimmatli   qog ' ozlar , [6]
  va   tugmachalarini   yaratish
Merkle - Hellman [7]
  va   boshqalar   ryukzak   kriptotizimlari .   Ruxsat   etilgan
algoritmlarning   dastlabki   qo'llanilishlaridan   biri   testlarni   tuzishda   va   skorlashda
bo'lib,   unda   test   topshiruvchilar   qaysi   savollarga   javob   berishlarini   tanlashi
mumkin.   Kichik   misollar   uchun   test   topshiruvchilarga   bunday   tanlovni   taqdim
etish juda oddiy jarayon. Masalan, agar imtihonda har biri 10 balldan iborat 12 ta
savol   bo'lsa,   test   topshiruvchisi   mumkin   bo'lgan   maksimal   100   ballga   erishish
uchun   faqat   10   ta   savolga   javob   berishi   kerak.   Biroq,   nuqta   qiymatlarining
heterojen   taqsimlanishiga   ega   bo'lgan   testlarda   tanlovni   ta'minlash   qiyinroq.
Feyerman va Vayss talabalarga jami 125 mumkin bo'lgan ball bilan heterojen test
beradigan   tizimni   taklif   qildilar.   Talabalardan   barcha   savollarga   o'zlarining
qobiliyatlari  bo'yicha   javob  berishlari   so'raladi.  Umumiy  bal   qiymati   100  ga  teng
bo'lgan   muammolarning   mumkin   bo'lgan   kichik   to'plamlari   ichida   ryukzak
algoritmi   qaysi   to'plam   har   bir   o'quvchiga   mumkin   bo'lgan   eng   yuqori   ballni
berishini aniqlaydi. [8]
Ta'rif:  Hal   qilinadigan   eng   keng   tarqalgan   muammo   bu   0-1  ryukzak   muammosi ,  bu
raqamni   cheklaydi   har   bir   turdagi   nusxalarning   nolga   yoki   bittaga   nusxalari .
To ' plami   berilgan   0   dan   1   gacha   raqamlangan   buyumlar ,   har   biri   og ' irlik   bilan   va
qiymat ,   maksimal   og ' irlik   hajmi   bilan   birga , maksimal   darajaga   ko ' tarish   uchun
mavzu   va .   bu   yerda   buyum   misollari   sonini   ifodalaydi   ryukzakchaga   qo ' shmoq .
Norasmiy   ravishda ,   muammo   ryukzaklar   summasi   ryukzakchaning   sig ' imidan
kichik   yoki   unga   teng   bo ' lishi   uchun   ryukzaklardagi   buyumlar   qiymatlari
yig ' indisini   maksimal   darajada   oshirishdan   iborat .
  Ryukzak   muammosi   ( BKP )   har   bir   elementdan   bittasi   bo ' lishi   haqidagi
cheklovni   olib   tashlaydi ,   ammo   raqamni   cheklaydi   har   qanday   turdagi nusxalarning   maksimal   manfiy   bo ' lmagan   butun   qiymatiga   nusxalari   : maksimal
darajaga   ko ' tarishv   uchun   mavzu   va   cheksiz   ryukzak   muammosi   ( UKP )   har
qanday   turdagi   nusxalar   soniga   yuqori   chegaralarni   qo ' ymaydi   va   yuqoridagi   kabi
tuzilishi   mumkin ,   faqat   bitta   cheklov   manfiy   bo ' lmagan   tamsay ı   ekanligi .
maksimal   darajaga   ko ' tarish   uchun   mavzu   va   chegarasiz   ryukzak   muammosining
bir   misoli   ushbu   maqolaning   boshida   ko ' rsatilgan   rasm   va   ushbu   rasm
sarlavhasidagi   " agar   har   bir   qutining   biron   bir   raqami   mavjud   bo ' lsa "   matnida
keltirilgan .
Cheksiz   ryukzak   muammosi   ( UKP )   har   qanday   turdagi   nusxalar   soniga
cheklov   qo ' ymaydi .   Bundan   tashqari ,   biz   buni   taxmin   qilamizuchun   mavzu   va
shunga   e ' tibor   bering   quyidagi   xususiyatlarga   ega :
1.(nol elementlarning yig'indisi, ya'ni bo'sh to'plamning yig'indisi).
2. qayerda ning qiymati - buyumning uchinchi turi.
Ikkinchi  xususiyatni  batafsil  tushuntirish kerak. Ushbu usulni  ishlatish jarayonida
biz   qanday   qilib   og'irlikni   olamiz   ?   Faqat   bor   yo'llari   va   oldingi   og'irliklari   jami
bo'lgan   joyda   turli   xil   narsalarning   turlari   (har   xil   deyish   bilan   biz   og'irlik   va
qiymat   bir  xil  emasligini  bildiramiz).  Agar  biz  bularning  har   bir  qiymatini  bilsak
narsalar   va   ular   bilan   bog'liq   maksimal   qiymat   ilgari,   biz   ularni   bir-birimiz   bilan
taqqoslaymiz va oxir-oqibat maksimal qiymatni olamiz va biz bajaramiz.
Bu   erda   bo'sh   to'plamning   maksimal   qiymati   nolga   teng.   Natijalarni   jadvalga
yozish   yuqoriga   yechimini   beradi.   Har   birining   hisob-kitobidan   beri   eng   ko'p
tekshirishni   o'z   ichiga  oladi   buyumlar   va   eng  ko'pi   bor   ning  qiymatlari   hisoblash
uchun   dinamik   dasturlash   yechimining   ishlash   vaqti   hisoblanadi.   Bo'linish   ular
tomonidan  eng katta umumiy bo'luvchi  bu ish vaqtini yaxshilashning bir usuli.
Xatto .. bo'lganda ham   P ≠ NP ,murakkablik, ryukzak muammosi ekanligiga
zid   emas   To'liq   emas ,   beri,   farqli   o'laroq,   masalaning   kiritilish   uzunligi   bo'yicha
polinom   emas.   Uzunligi   masalaning   kiritilishi   bitlar   soniga   mutanosib   emas   o'zi.
Biroq,   bu   ish   vaqti   bo'lgani   uchun   psevdopolinomiya ,   bu   (qarorning   versiyasi)
ryukzak muammosini keltirib chiqaradi a  zaif NP bilan to'ldirilgan muammo .
Yaqinlashish algoritmlari NP   bilan   to'ldirilgan   ko'pgina   muammolarga   kelsak,   ular   maqbul   bo'lmasa
ham,   ularni   echish   mumkin.   Biroq,   tarjixon,   yaqinlashuv   topilgan   eritma   qiymati
va   optimal   eritmaning   qiymati   o'rtasidagi   farq   kafolati   bilan   birga   keladi.Ko'p
foydali, ammo hisoblashda murakkab algoritmlarda bo'lgani kabi, yechimni taxmin
qiladigan   algoritmlarni   yaratish   va   tahlil   qilish   bo'yicha   jiddiy   tadqiqotlar
o'tkazildi. NP-Hard bo'lsa-da, ryukzak muammosi hali ham har qanday belgilangan
darajaga   yaqinlashtirilishi   mumkin   bo'lgan   algoritmlar   to'plamidan   biridir.   Bu
shuni  anglatadiki, masalaning  polinom  vaqtni  taxminiy sxemasi  mavjud. Aniqroq
aytganda,   ryukzak   muammosi   to'liq   polinomiyali   vaqtni   taxminiy   sxemasiga
(FPTAS) ega.
Vaqtni to'liq polinomga yaqinlashtirish sxemasi
To'liq polinom vaqtni taxminiy sxemasi  (FPTAS) ryukzak muammosi uchun
muammoning   ma'lum   vaqt   polinom   yechimlari   yo'qligi   sababi,   ob'ektlar   bilan
bog'liq   foyda   cheklanmaganligidadir.   Agar   foyda   qiymatlarining   bir   nechta
ahamiyatsiz raqamlarini yaxlitlasa, u holda ular polinom bilan chegaralanadi va 1 /
ε   bu erda   ε   yechimning to'g'riligiga bog'liqdir. Keyinchalik, bu cheklash algoritm
polinom   vaqtida   optimal   yechimning   (1- ε )   faktori   ichida   to'g'ri   yechimni   topishi
mumkinligini  anglatadi. A lgoritm   FPTAS   bu   kiritish:   ε   ∈   (0,1] qiymatlari  bilan
ko'rsatilgan n elementlarning A ro'yxati, va og'irliklar   chiqish:   S 'FPTAS yechimi
P: = max // elementning eng yuqori qiymati K: =   ε   uchun   men   dan   1   ga   n   qil   :=
uchun   tugatish   qaytish   yordamida   S   'eritmasi   yuqorida   ko'rsatilgan   dinamik
dasturdagi qiymatlar.
Teorema: To'plam   yuqoridagi   algoritm   bilan   hisoblangan,   qayerda   eng   maqbul
yechimdir.
Hukmdorlik munosabatlari
Hech   qachon   kerak   bo'lmagan   narsalarni   tashlab,   cheksiz   ryukzak
muammosini   echish   osonroq   bo'ladi.   Berilgan   element   uchun,   biz   narsalar
to'plamini   topdik   deylik   shundayki   ularning   umumiy   vazni   og'irligidan   kam,   va
ularning   umumiy   qiymati   ning   qiymatidan   katta.   Keyin   optimal   yechimda ko'rinmaydi,   chunki   har   qanday   potentsial   yechimni   har   doim   yaxshilay   olamiz
almashtirish   bilan   to'plam   bilan.   Shuning   uchun   biz   umuman   olganda.   Bunday
hollarda,   deyiladi   hukmronlik   qilish .   (Shuni   yodda   tutingki,   bu   cheklangan
ryukzak muammolariga taalluqli emas, chunki biz allaqachon elementlarni ishlatib
yuborganmiz).Dominantlik   munosabatlarini   topish   qidiruv   maydonining   hajmini
sezilarli darajada kamaytirishga imkon beradi. Bir necha xil turlari mavjud  ustunlik
munosabatlari , [11]
 barchasi shaklning tengsizligini qondiradi va kimdir uchun
qayerdava. Vektor har bir a'zoning nusxalari sonini bildiradi.
Modul ustunligi
Ruxsat bering bo'lishi   eng yaxshi buyum , ya'ni Barcha uchun . Bu qiymatning eng
katta zichligi bo'lgan element. - uchinchi element   modulli hukmronlik qilmoqda
bitta   element   bilan   sifatida   yozilgan   ,   agar   ustunlik   qiladi   ortiqcha   bir   nechta
nusxalari . Rasmiy ravishda, bo’ldi.
Ko'p ob'ektivli ryukzak muammosi
Ushbu   xilma-xillik   ryukzakchani   to'ldirayotgan   shaxsning   maqsadini
o'zgartiradi. Pul foydasini ko'paytirish kabi bitta maqsad o'rniga, maqsad bir necha
o'lchovlarga   ega   bo'lishi   mumkin.   Masalan,   ekologik   yoki   ijtimoiy   muammolar,
shuningdek   iqtisodiy   maqsadlar   bo'lishi   mumkin.   Portfolio   va   transport
logistikasini   optimallashtirishni   tez-tez   hal   qilinadigan   muammolar.   Misol
tariqasida   siz   kruiz   kemasini   boshqargansiz.   Siz   qancha   taniqli   komediyachilarni
yollash   kerakligini   hal   qilishingiz   kerak.   Ushbu   qayiq   bir   tonnadan   ortiq
yo'lovchini   qabul   qila   olmaydi   va   ko'ngilocharlarning   vazni   1000   funtdan   kam
bo'lishi kerak. Har bir komediyachining vazni bor, mashhurligi asosida biznes olib
boradi  va aniq maosh so'raydi. Ushbu misolda siz bir nechta maqsadlarga egasiz.
Siz,   albatta,   sizning   maoshingizni   minimallashtirish   bilan   birga,   ko'ngil
ochuvchilarning   mashhurligini   maksimal   darajada   oshirishni   xohlaysiz.   Bundan
tashqari, siz iloji boricha ko'proq ko'ngilocharlarga ega bo'lishni xohlaysiz. Aytaylik, birinchi element, ikkinchi element esa,. Shartni ikkita bir o'lchovli
yoki bitta ikki o'lchovli massivda ko'rib chiqqandan so'ng (siz xohlaganingizcha).
Keling,   bir   o'lchovli   massiv   yarataylik,   uning   o'lchami   teng   bo'ladi   va   birinchi
element   0   ga   teng   bo'ladi,   qolganlari   esa   minus   cheksizlikka   teng   bo'ladi   yoki
bizning   holatimizda   (kodda)   -1   ga   teng   bo'ladi.   (1-rasm).   Va   keyin,   (2-rasm)
ko'rsatilgandek,   buyumning   vazn   raqamiga   ega   elementdan   boshlab,   biz   kodda
ko'rsatilgandek,   biz   uning   narxini   oldingisining   narxiga   qo'shamiz   s   [j]   =   s   [j   -
WeiCos   [i   ]   [0]]   +   WeiCos   [i]   [1];   agar   o'tmish   minus   cheksizlik   bo'lmasa.   Va
ikkinchi element bilan, ular birinchisi bilan kesishganda, biz ularni solishtiramiz va
ularni   kattaroq   massivga   joylashtiramiz.   Va   eng   oxirida,   biz   yana   massivdan
o'tamiz va qaerda bo'lishidan qat'i  nazar, eng katta elementni tanlaymiz (3-rasm).
Va   shunday   qilib,   vaznga   teng   bo'lgan   oxirgi   pozitsiyalarda,   hujayralardagi   eng
qimmat elementlarning qayd etilishi tufayli eng qimmat kombinatsiyalar yoziladi.
 Ko'p o'lchovli ryukzak muammosi
Ushbu xilma-xillikda ryukzak buyumining og'irligi D o'lchovli vektor bilan
berilgan   va   ryukzak   D   o'lchovli   sig'im   vektoriga   ega   .   Maqsad   -   ryukzakchadagi
narsalar   qiymatlari   yig'indisini   maksimal   darajada   oshirish,   shunda   har   bir
o'lchovdagi og'irliklar yig'indisi oshmaydi.
Ko'p   o'lchovli   ryukzak,   ryukzakchaga   qaraganda   hisoblash   qiyinroq;   uchun   ham,
muammo yo'q   EPTAS   agar P NP. [23]
  Biroq, algoritm [24]
  siyrak misollarni samarali
echish   uchun   ko'rsatilgan.   Agar   to'plam   mavjud   bo'lsa,   ko'p   o'lchovli
ryukzakchaning misoli juda kam uchun Shunday qilib, har bir ryukzak uchun ,shu
kabi   va   .   Bunday   holatlar,   masalan,   o'rni   tugunlari   bo'lgan   simsiz   tarmoqdagi
paketlarni rejalashtirishda yuz beradi. [24]
 Dan algoritm [24]
 shuningdek, ko'p variantli
variantning siyrak holatlarini, ko'p tanlovli ko'p o'lchovli ryukzakchani hal qiladi.
IHS   (Balandlikning   ko'tarilishi)   algoritmi   2   o'lchovli   ryukzak   (kvadratlarni   ikki
o'lchovli   o'lchov   birligi   kvadratiga   o’tkazish)   uchun   eng   maqbuldir:   optimal
o’tkazishda ko'pi bilan besh kvadrat mavjud bo'lganda. [25] Bir nechta ryukzak muammosi
Ushbu   o'zgaruvchanlik   o'xshash   Chiqindilarni   o’tkazish   muammosi .   Bu   qutilarni
o’tkazish   muammosidan   farqi   shundaki,   buyumlar   to'plamini   tanlash   mumkin,
ammo   qutilarni   o'rash   muammosida   barcha   narsalar   ma'lum   qutilarga
joylashtirilishi   kerak.   Kontseptsiya   shundaki,   bir   nechta   knopkalar   mavjud.   Bu
ahamiyatsiz o'zgarish bo'lib tuyulishi mumkin, ammo bu dastlabki ryukzakchaning
imkoniyatlarini   qo'shishga   teng   emas.   Ushbu   o'zgarish   Operations   Research-dagi
ko'plab   yuklash   va   rejalashtirish   muammolarida   qo'llaniladi   va   a   Polinom-vaqtni
taxminiy sxemasi . [26]
Kvadratik biriktirish muammosi
Kvadratik  knopka   masalasi   ikkilik   va  chiziqli   sig'im   cheklovlariga  bo'ysunadigan
kvadratik   funktsiyani   maksimal   darajaga   ko'taradi. [27]
  Muammoni   Gallo,   Hammer
va Simeone 1980 yilda kiritgan, [28]
 ammo muammoni birinchi davolash 1975 yilda
Vitzgallga tegishli. [29]
Jami summa muammosi
  Pastki   yig'indisi   muammosi   bu   qarorning   maxsus   holati   va   har   qanday
buyumning vazni qiymatga teng bo'lgan 0-1 muammolari: . Sohasida  kriptografiya ,
atama   ryukzak   muammosi   ko'pincha   subset   sum   muammosiga   maxsus   murojaat
qilish   uchun   ishlatiladi   va   odatda   biri   sifatida   tanilgan   Karpning   21   ta   NP-ning
to'liq muammolari . [30]
Jami   summa   masalasini   umumlashtirish   bir   nechta   sig'imlar   bir   xil   imkoniyatga
ega   bo'lgan   bir   nechta   yig'indilar   yig'indisi   muammosi   deb   ataladi.
Umumlashtirishda FPTAS yo'qligi ko'rsatildi. [31]
Orqa   ryukzak   vazifasi   ( shuningdek ,   naqsh   vazifasi )- NP   kombinatorni
optimallashtirishning   to ' liq   vazifasidir .   Uning   nomi   yakuniy   maqsaddan   olingan :
ryukzak   hajmi   cheklangan   bo ' lsa ,   ryukzak   ichida   imkon   qadar   ko ' p   qimmatbaho
narsalarni   qo ' yish .   Ryukzak   vazifasining   turli   xil   variantlari   bilan   iqtisodiyot ,
amaliy   matematika ,  kriptografiya   va   logistika   sohalarida   duch   kelish   mumkin . Umuman   olganda ,   vazifa   quyidagicha   ifodalanishi   mumkin :   " qiymat "   va
" og ' irlik "   xususiyatlariga   ega   bo ' lgan   ko ' plab   ob ' ektlardan   maksimal   to ' liq   qiymat
bilan   pastki   qismni   tanlash   kerak ,  bu   esa   umumiy   vaznga   cheklovni   kuzatadi .
Tarkib
1 klassik muammo bayonoti
Har birining ikkita parametri — massa va qiymati bo'lgan bir qator narsalar
bo'lsin.   Bundan   tashqari,   ma'lum   bir   yuk   hajmi   bir   ryukzak   bor.   Muammo
shundaki,   ryukzakning   umumiy   massaga   cheklanishiga   rioya   qilib,   ichidagi
narsalarning maksimal qiymati bilan ryukzak yig'ishdir.
kattaroq qilish         va 
Orqa ryukzaki haqida vazifalar
Asosiy maqola: ryukzak haqida vazifalar ro'yxati
Muammoni   shakllantirish,   ryukzak,   narsalar   yoki   ularning   tanloviga
qo'yiladigan   shartlarga   qarab,   juda   ko'p   umumlashmalarga   imkon   beradi.   Eng
mashhur navlar quyidagilardir:
Orqa   xalqa   0-1   (eng.   0-1   Knapsack   Problem)[2]:   har   bir   elementning   bir   nechta
nusxasi.
Cheklangan   ryukzak   (eng.   Bounded   Knapsack   Problem)[3]:   har   bir
elementning muayyan sonidan ortiq emas. Cheksiz ryukzak (ingliz tili. Unbounded
Knapsack Problem) [3]: har bir elementning tasodifiy soni. Ko'p tanlovli ryukzak
(ingliz tili. Multiple-choice Knapsack Problem) [4]: mavzular guruhlarga bo'linadi
va har bir guruhdan faqat bitta elementni tanlash kerak. Bir nechta ryukzak (ingliz
tili.   Multiple   Knapsack   Problem)[5]:   bir   nechta   ryukzak   bor,   ularning   har   biri
maksimal og'irligi bilan. Har bir element har qanday ryukzak ichiga qo'yilishi yoki qoldirilishi   mumkin.   Ko'p   o'lchovli   ryukzak   (ingliz   tili.   Multi-dimensional
knapsack problem): og'irlik o'rniga bir nechta turli resurslar (masalan, vazn, hajm
va uslublar vaqti) beriladi. Har bir mavzu har bir resursning belgilangan miqdorini
sarflaydi.   Har   bir   resursning   umumiy   xarajatlari   ushbu   manbadan   maksimal
darajada   oshmasligi   uchun   ob'ektlarning   pastki   qismini   tanlash   kerak   va   ayni
paytda   ob'ektlarning   umumiy   qiymati   maksimal[4].   Orqa   ryukzakning   kvadrat
vazifasi (ingliz tili. Asosiy siyosiy partiyalari va kasaba uyushmalari[tahrir]
Orqa ryukzakning chiziqli vazifasi. Orqa ryukzak vazifasining eng keng tarqalgan
variantlaridan biri chiziqli emas. U quyidagicha ifodalanishi mumkin:
Vektor   qilaylik   rishtadagi   har   bir   elementning
nusxalari sonini aniqlaydi. Keyin vazifa minimal funktsiyani topishdir
Vazifalar   uzluksiz   va   differentsiatsiya   qilingan   deb   taxmin
qilinadi vazifa to'siqqa qarab klassik ishlab chiqarishlardan biriga tushadi
 - ryukzak 0-1          - cheksiz ryukzak
 - cheklangan ryukzak
Vazifalarni   tanlash   erkinligi     f   (x),   g(x)   agar   ishlab   chiqarish   salohiyatini
tashkil   etish,   shu   jumladan,   vazifalar   kengroq   sinf,   hal   qilish   imkonini   beradi
(eng.)rus.,   rayonlashtirilgan   namunadagi   sempllarning   optimal   taqsimlanishi   yoki
orqa ryukzakda kvadrat vazifasini hal qilish[7].
Aniq hal usullari
Yuqorida   aytib   o'tilganidek,   ryukzak   vazifasi   NP   sinfiga   tegishli-to'liq   va
uning   uchun   o'rtacha   vaqt   ichida   hal   qiluvchi   polinom   algoritmi   topilmadi.
Shuning   uchun,   ryukzak   muammosini   hal   qilishda   siz   "katta"   orqa   ryukzaklar
uchun qo'llanilmaydigan aniq algoritmlar va tezkor ishlaydigan, ammo muammoni
optimal echishga kafolat bermaydigan taxminiy algoritmlarni tanlashingiz kerak.
To'liq qidirish Boshqa   alohida   vazifalar   singari,   ryukzak   muammosi   ham   barcha   mumkin
bo'lgan yechimlarni to'liq bartaraf etish yo'li bilan hal qilinishi mumkin.
Muammoning   holatiga   ko'ra,   bir   ryukzak   ichiga   joylashtirilishi   mumkin
bo'lgan   narsalarning   n   mavjud   va   og'irligi   W   dan   oshmagan   yukning   maksimal
qiymatini aniqlash kerak.
Har   bir   element   uchun   2   variantlari   mavjud:   ob'ekt   bir   ryukzak   ichiga
qo'yiladi yoki ob'ekt orqa ryukzakchaga joylashtirilmaydi. So'ngra, barcha mumkin
bo'lgan variantlar  busting u faqat  ob'ektlar  kichik miqdorda foydalanish  imkonini
beradi   O(n2),   vaqtinchalik   murakkabligi   bor[8].   Ob'ektlar   sonining   ko'payishi
bilan, vazifa maqbul vaqt uchun bu usul bilan hal qilinmaydi.
Rasmda   uchta   ob'ekt   uchun   busting   daraxti   ko'rsatilgan.   Har   bir   varaq
ob'ektlarning bir qismiga mos keladi. Yog'och tuzilgandan so'ng, og'irligi W[9] dan
oshmagan kishilar orasida maksimal qiymatga ega bo'lgan varaqni topish kerak.
Uchta element uchun yechim topishga mos keladigan to'liq qidiruv daraxti.
Har   bir   tugunda   bu   element   bir   ryukzak   ichiga   qo'yiladimi   yoki   yo'qligini
aniqlaydi.  Tugundagi   raqam   ob'ekt   raqamiga   mos   keladi.   Qovurg'adagi   raqamlar:
0-bu narsa olingan emas, degan ma'noni anglatadi, 1-bu nima edi.
Filiallar va chegaralar usuli Filiallar va chegaralar usuli-bu butunlay qidirish usulining o'zgarishi bo'lib,
u   butunlay   qidirish   daraxtining   ataylab   optimal   bo'lmagan   filiallari   chiqarib
tashlanadi. To'liq qidirish usuli kabi, u eng yaxshi yechimni topishga imkon beradi
va   shuning   uchun   aniq   algoritmlarga   ishora   qiladi.Piter   Kolesar   tomonidan   taklif
etilgan   original   algoritm   (eng.   1967   yilda   Piter   Kolesar   ob'ektlarni   o'ziga   xos
qiymatiga (og'irlik qiymatiga nisbatan) qarab tartiblashni va to'liq qidirish daraxtini
qurishni   taklif   qiladi.   Uning   yaxshilanishi   shundaki,   har   bir   tugun   uchun   daraxt
qurish   jarayonida   yechim   qiymatining   yuqori   chegarasi   baholanadi   va   daraxtni
faqat   maksimal   qiymatga   ega   bo'lgan   tugun   uchun   qurish   davom   etadi[10].
Maksimal yuqori chegara daraxt bargida bo'lsa, algoritm o'z ishini tugatadi.
Filiallar   va   chegara   usullarining   busting   variantlari   sonini   kamaytirish
qobiliyati   kirish   ma'lumotlariga   asoslanadi.   Bu   ob'ektlar   o'ziga   xos   qadriyatlar
sezilarli darajada farq bo'lsa, faqat foydalanish tavsiya etiladi[11].
0-1 ryukzak vazifasi
0-1 orqa ryukzaksi  haqidagi  muammoni  hal  qilish  oldingi  muammoni  hal  etishga
yaqin, ammo har bir ob'ekt bitta nusxada mavjudligini hisobga olish kerak.  m[i,w]
— birinchi {\displaystyle i}i dan olingan narsalarning maksimal qiymati, umumiy
og'irligi w dan oshmasin.
Qayta tiklash nisbati:
yoki
yoki
Hisoblash     m[n,W]   aniq   bir   yechim   topish   mumkin.   Agar   array   m[i,   w]mashina
xotirasida   joylashtirilgan   bo'lsa,   bu   algoritm,   ehtimol,   eng   samarali[12]   biri
hisoblanadi. Dinamik dasturlash usuli bilan yechimni quyidagi tarzda ko'rsatish mumkin
x   o'qi   bo'ylab   ikki   o'lchovli   tekislikda,   y   o'qi   bo'ylab   —   ularning   vazni.
Koordinatalar   boshidan   boshlab   birinchi   bosqichda   ikkita   chiziq   quriladi:
gorizontal,   birinchi   ob'ekt   olinmaganiga   va   birinchi   mavzuga   mos   keladigan
moyillikka   mos   keladi.   Ularning   proektsiyalari   y   o'qi   ob'ektning   vazniga   teng.
Ikkinchi bosqichda yana 2 liniyasi quriladi, gorizontal( ikkinchi ob'ekt olinmagan)
yoki eğimli (ikkinchi ob'ekt olinadi). Gorizontal yoylarning uzunligi nolga teng va
obliquely — ob'ektning qiymatini qo'ying [14].
Shunday qilib, har qanday muammoni hal qilish qurilgan daraxtda bir yo'lga
to'g'ri keladi. Vazifa maksimal uzunligi[14] yo'lini topish uchun kamayadi.
Orqa o'rindiqning hajmi bo'lsin .
Orqa   ryukzakni   to'ldirishni   tasvirlaydigan   tarmoq.   Kvadrat   qavslar
algoritmning ushbu bosqichida umumiy qiymatni ko'rsatadi, optimal yechim doira
bilan belgilanadi
Genetik algoritmlar
Boshqa   NP-optimallashtirish   qiyin   vazifalar   kabi,   ryukzak   muammoni   hal
qilish   uchun   genetik   algoritmlarni   ishlatiladi.   Ular   polinom   vaqt   uchun   optimal
yechim   topish   kafolat   va   optimal   hal   yaqinlik   baholash   bermaydi,   lekin   tezroq
boshqa   ma'lum   deterministik   yoki   Heuristic   usullari   ancha   yaxshi   yechim   topish
imkonini   beruvchi,   yaxshi   vaqt   ko'rsatkichlari   bor.Har   bir   shaxs   (genotip)   -   biz
to'plamoqchi bo'lgan narsalarning kichik to'plami (ularning umumiy og'irligi ruxsat
etilgan   yuk   hajmidan   oshib   ketishi   mumkin).   Qulaylik   uchun   ma'lumot   har   bir
bitning   ob'ektga[19]   joylashtirilganligini   aniqlaydigan   ikkilik   qatorlar   shaklida
saqlanadi.
Moslashuvchanlik   funktsiyasi   eritmaning   maqbulligiga   yaqinligini
aniqlaydi.   Misol   uchun,   bu   umumiy   og'irlik   yuk   tashish   hajmidan   oshmasa,
ob'ektlarning umumiy qiymati sifatida xizmat qilishi mumkin.Eng moslashtirilgan
shaxslar   kesib   va   qolgan   e'tiborsiz   bo'lgan   avlodlar   smenada   bir   qator   so'ng,
algoritm, taxmin, original yechimlar yaxshilash kerak. Genetik   algoritmdan   foydalangan   holda   aholining   evolyutsiyasi   misoli.
Ob'ektlar   ikki   tomonlama   shaklda   kodlovchi   chiziqlar   bo'lib,   ular   orqa   o'rindiqqa
qanday   narsalar   qo'yiladi.   Misol   uchun,   chiziq   (0,1,0,1,0)   12   kg   va   7   kg
og'irlikdagi qutilarni tanlashga mos keladi .
Kichik guruhlar miqdori bo'yicha muammoni hal qilish
Orqa   ryukzaksi   vazifasining   maxsus   ishi-bu   kichik   to'plamlarning   miqdori.
W   —   Ryukzak   yuk   hajmi,   w_{i}—   og'irligi   va   uning   qiymati   v_{i}=w_{i}   .
Shunday   qilib,   qiyinchilik,   orqa   ryukzakni   eng   qattiq   yoki   to'liq   resurslarni
sarflashdir:
Ushbu genetik algoritmni hal qilish uchun foydalanishingiz mumkin. Shaxs
vektor .   W   dan   kam   ob'ektlar   umumiy   og'irligi   bir   ryukzak   ichiga
joylashtirilgan yana afzal fotoalbomlarda faqat xususiyati bilan, W uchun ob'ektlar
umumiy og'irligi yaqinlik foydalanish kerak moslashish vazifasi sifatida.
Rasmiy   ravishda   moslashuvchanlik   funktsiyasini   aniqlang
.   Unga   ruxsat   bering —   barcha   elementlarning
miqdori.   Keyin orqa   yuzdagi   narsalarning   vazni
maksimal darajada o'zgarishi . Unga   ruxsat   bering -   ushbu   vektor   uchun   ob'ektlarning   umumiy
og'irligi. Keyin qo'ying:
Orqa ryukzak vazifasi bilan shifrlash
Umumiy shakldagi rishta muammosi aniq qabul qilinadigan vaqt uchun hal
etilmasligi   sababli,   u   kriptografik   vazifalarda   ishlatilishi   mumkin.   Buning   uchun
ommaviy   ravishda   ma'lum   bo'lgan   narsalar   to'plami   bilan   biz   xabarni   uzatilgan
narsalar   to'plami   sifatida   taqdim   etamiz   va   ularning   umumiy   og'irligini[28]
yuboramiz.   agar   muallif   mualliflik   ma'lumotlarni   tekshirish
mumkin muallifi sekin nomi bilan yuqorida berilgan foto uchun original sahifaga
sizni olib boradi.
Ryukzak   vektor   ochiq   kalit   hisoblanadi.   Ochiq   matnni   shifrlash   uchun   bit
uzunlikdagi   bloklarga   bo'linadi,   har   bir   bit   esa   orqa   ryukzakda   elementning
mavjudligini   aniqlaydi   (masalan,   ochiq   matn   (111100)   orqa   ryukzakda   oltita
mumkin   bo'lgan   narsalarning   dastlabki   to'rtdan   biriga   mos   keladi).   Bu   birlik
ryukzak   ichida   ob'ekt   mavjudligini   ko'rsatadi,   deb   ishoniladi,   va   uning   yo'qligi
uchun nol. Shundan so'ng, bu ochiq matn uchun ryukzak ichida ob'ektlar umumiy
og'irligi hisoblab, va shifrotext sifatida uzatiladi[28].Ushbu algoritm bilan shifrlash
misoli:Bir   ryukzak   vektor   belgilangan   bo'lsin   a=(3,4,6,7,10,   11)   uzoq   n=6   bilan
Aniqlash
Orqa ryukzak vazifasini shakllantirish
Keling, orqa ryukzaki haqidagi muammoning klassik formulasini keltiraylik
(naqsh vazifalari).Vaziyat: massa uchun cheklangan quvvatga ega ryukzak mavjud;
shuningdek, ma'lum bir og'irlik va qiymatga ega bo'lgan narsalar to'plami mavjud. Bunday   narsalarni   tanlash   kerak,   shunda   u   orqa   ryukzakga   joylashtiriladi   va
maksimal qiymatga (narxga) ega bo'ladi.
Ryukzak muammosini hal qilish algoritmi
Bir   ryukzak   muammosini   aniq   hal   qilishning   eng   oddiy   usullaridan   birini   ko'rib
chiqing: bu to'liq qidirish usuli.Biz v kabi naqshning maksimal  og'irligini va turli
xil   narsalar   sonini   belgilaymiz   N.   to'plamda   mutlaqo   bir   xil   narsalar   bo'lishi
mumkin.Har bir element: ism, vazn va xarajat (qiymat):
Ismi Vazn   Qiymati
Kitob 1 600
Dürbün 2 5000
Muammoni   hal   qilish   uchun   siz   ob ' ektlar   to ' plamlarining   barcha
kombinatsiyalarini   yaratishingiz   va   massasi   W   dan   ortiq   bo ' lmagan   to ' plamni
tanlashingiz   kerak   va   umumiy   xarajat   ( boshqa   mos   keladigan   to ' plamlarga
nisbatan )   maksimal   darajada . Kombinatorika   shartlari   doirasida ,   bu   N .   ning   barcha
o ' zgarishlarini   ko ' rib   chiqish   kerakligini   anglatadi .
Agar beshta narsa bo'lsa, 5 ni ko'rib chiqing! = 120 turli xil narsalar.
Shubhasiz,   ryukzak   muammosini   hal   qilish   uchun   to'liq   qidirish   algoritmining
hisoblash   murakkabligi   o   (n!).Barcha   narsalarni   to'liq   qidirish   usulining   salbiy
tomoni shundaki, agar narsalar soni katta bo'lsa, unda algoritm maqbul vaqt uchun
qaror qabul qilmaydi, chunki faktorial juda tez o'sib borayotgan xususiyatdir. Xulosa
To'liq  qidiruv  usuli   juda mashaqqatli  bo'lgani  uchun,  ryukzak  hajmi   va uni
ishlatishda   elementlar   soni   cheklangan   bo'lishi   kerak.Shuning   uchun   bu   usul
cheksiz   va   uzluksiz   uchun   qo'llanilmaydi   ryukzaklar.   Ko'paytma   va   cheklangan
masalalarni sanab o'tish orqali hal qilishda ryukzaklar, siz elementlarning sonini 10
tagacha   kamaytirishingiz   kerak,   shunda   yechim   bo'ladi   topildi.Muammolarni
echishda tarmoqli va chegara algoritmining aniq kamchiliklari katta hajm - bu juda
ko'p narsalarni takrorlash zarurati optimalni topishdan oldin variantlar. Shubhasiz,
dallanish usuli  qidiruvni takrorlaydi. Biroq, "foydasiz" yechimlarni kesib tashlash
orqali,   bu   mumkin   cheksiz   yechim   maydonini   mustaqil   ravishda   cheklaydi.
Shuning uchun bo'lishi  mumkin cheksiz ryukzak uchun amal  qiladi, lekin doimiy
uchun   qo'llash   mumkin   emas   ryukzak.   Ochko'z   algoritm   bir   mezonli   algoritm,
shuning uchun ko'p o'lchovli ryukzak uchun qo'llanilmaydi. Biroq, muammo uchun
ekanligini ta'kidlash kerak uzluksiz ryukzak - bu eng maqbul yechimni topadigan
algoritm.   Genetik   algoritm   eng   tezkor   algoritmlardan   biridir.   Lekin   bu
algoritmning   cheklanishi   shundaki,   uning   xromosomalari   diskret   kodlangan.
Shunga ko'ra, uni doimiy va cheksiz hal qilish uchun ishlatib bo'lmaydi vazifalar.
Genetik   algoritmning   yana   bir   kamchiligi   shundaki,   u   kafolat   bermaydi   ba'zi
vaziyatlarda optimal yechimni topish (mahalliy topadi global o'rniga ekstremum).
Bu   algoritm   mumkinligi   bilan   bog'liq   optimal   yechimga   erishilgandagina   emas,
balki   quyidagi   bilan   ham   yakunlanadi   shartlar:   takrorlashning   belgilangan
maksimal   sonidan   o'tgan;   algoritmni   bajarish   uchun   belgilangan   maksimal   vaqt
o'tdi; yangi avlodga o'tishda sezilarli o'zgarishlar sodir bo'lmaydi. Adabiyotlar
1. Левитин   А.   В.      Алгоритмы.   Введение   в   разработку   и   анализ   —
М.:  Вильямс , 2006. — С. 160—163. — 576   с. —  ISBN 978-5-8459-
0987-9
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. Бурков В. Н.    ,   Горгидзе И. А. ,   Ловецкий С. Е.   Прикладные задачи
теории   графов   /   под   ред.   А.   Я.   Горгидзе   —   Тбилиси :
Вычислительный центр АН СССР , 1974. — 231 с.
5. В. Н. Бурков, Д. А. Новиков.   Эkменты теории графов . — 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 .   Архивная копия  от 18
декабря 2018 на  Wayback Machine
8. А.   Саломаа.   Криптография   с   открытым   ключом   =   Public-Key
Cryptography.   —   М.:   Мир,   1995.   —   С.   102-150.   —   ISBN   5–03–
001991–X.   Архивная копия   от 4 марта 2016 на   Wayback Machine 9. Н.   Коблиц.   Курс   теории   чисел   в   криптографии.   —   2-ое.   —   М.:
Научное   издательство   ТВП,   2001.   —   С.   254.   —   ISBN   5-85484-
014-6 .
10. Габидулин   Э. М.    ,   Кшевецкий   А.  С. ,   Колыбельников  А. И.   Защита
информации : учебное  пособие   — М.:   МФТИ , 2011. — 225   с. —
ISBN 978-5-7417-0377-9
11. Осипян   В.   О.   О   системе   защиты   информации   на   основе
пробkмы   рюкзака   //   Известия   Томского   политехнического
университета [Известия ТПУ]. — 2006. —  Т. 309 ,  № 2 . —  С. 209-
212 .

“Ryukzak masalasi ” MUNDARIJA: 1.Kirish 2.Ryukzak muammosi 3. Hisoblashning murakkabligi 4.Oldindan algoritmni dinamik dasturlash 5.hukmdorlik munosabatlari 6.Kop ob’yektli ryukzak muammosi 6.ko’p o’lchovli ryukzak muammosi 7.Bir nechta ryukzak muammosi 8.Jami ryukzak muammosi 9.XULOSA 10.ADABIYOTLAR

Kirish Bugungi kunda ishlatilgan barcha narsalar mamlakat loyiha boshqaruvi usullari va modellari ijrochilar darajasiga mo'ljallangan: loyiha menejerlari, boshqaruv jamoasi, barcha zarur resurslar bilan jihozlangan mutaxassislar. Yuqori darajalar uchun iqtisodiyotni boshqarish-tarmoqlar, davlat korporatsiyalari, xoldinglar darajasi-loyiha boshqaruvining tegishli modellari va usullari ishlab chiqilmagan. Biroq, bu strategik qarorlar qabul qilish darajasi, 50 haqida unga bog'liq% loyiha faoliyatining muvaffaqiyati, barcha resurslar unga qaratilgan va eng muhim qarorlar qabul qilinadi. [1, p. 3] bu miqdor qayd etiladi muvaffaqiyatli loyihalar uchun muvaffaqiyatsiz loyihalar mamlakatimizda turli hisob-kitoblarga ko'ra, 40 dan 60% gacha. Shuning uchun, loyiha boshqarish qobiliyatsiz asosiy sabablaridan biri hisoblanadi,yuqori boshqaruv darajalari kam ishtirok etadi ushbu faoliyatda va zamonaviy metodologiya va loyihani boshqarish texnologiyasi hisobga olinmaydi ularning manfaatlari etarli darajada.Xorijda loyiha ehtiyoj ilmiy-tadqiqot va rivojlantirish boshqarish, va, xususan, uning yuqori darajasi uzoq vaqt davomida amalga oshirilgan. Bu yaratilganidan dalolat beradi va PATTERN [2]kabi tizimlarning ishlashi, QUEST [3], TORQUE [4], PPB [5], PROFILE [6], 60-yillarning oxirida AQShda yaratilgan. Ushbu tizimlarning barchasi rejalashtirish ob'ektining "maqsad-vazifalar" daraxti shaklida turli parametrlar, qiymatlar bilan tavsiflanadi ular ekspert baholarini qayta ishlash yo'li bilan belgilanadi. O'ziga xos xususiyati ushbu kompleks rejalashtirish sxemalari bir model sifatida ishlatiladi raqamli qiymatlar (masalan, yillik xarajatlar mavzu bo'yicha) va miqdoriy ko'rsatkichlarning ekspert baholashlari. Biroq, bu holat emas texnikadan keng foydalanishga to'sqinlik qiladi ma'lumotlarni tayyorlash uchun belgilangan sinf investitsiya siyosatini amalga oshirish va yirik innovatsiyalarni moliyalashtirish bo'yicha yuqori darajadagi boshqaruv qarorlarini qabul qilish loyihalar. 1978da mamlakatimizda bunday maqsadlar uchun analitik vosita sifatida taklif qilindi dastur-maqsadli ierarxik sxemalar usuli ilmiy-tadqiqot va

rivojlantirish rejalashtirish [7]. Ushbu usulning afzalligi ekspert baholarini qo'llash uchun yaxshi mo'ljallangan qurilma, qaror qabul qiluvchi shaxs (LPR) rejani belgilaydi, mezonlarni mustaqil ravishda ko'rsatadi va ularga subyektiv bo'lmagan hisob-kitoblarni beradi qabul qilingan rejani ham tuzatadi. Ushbu texnikada baholash mezonlarining ikkilik tabiati va hal qiluvchi qoidalarning oddiy tuzilishi LPRNI belgilangan maqsadlarga muvofiq cheklangan resurslarni taqsimlash vositasini taqdim etadi dastlabki investitsiya siyosatini interaktiv tarzda o'zgartirish uchun. Biroq, bu sodir bo'ladi tavsiya etilgan yechim olib keladigan holatlar ba'zi past-ustuvor loyihalarni moliyalashtirish voz va o'zgartirish kerak tashkil etilgan tashkiliy tuzilma. Shunday qilib, samarali model va algoritmlarni ishlab chiqish zarurati paydo bo'ladi kichik tizim bo'lishi kerak bo'lgan bunday loyiha boshqaruv tizimining yuqori darajasi uchun qurilma amalga oshiriladigan loyihalar portfelini tanlash va boshqarish. Ushbu maqolada loyihalar portfelining maqbul tanlovi va taqsimoti ko'rib chiqildi uni amalga oshirish uchun resurslar alohida vazifa shaklida optimallashtirish-ryukzak haqida ko'p o'lchovli vazifa.

Ryukzak muammosi Hozirgi vaqtda texnologik va ilmiy taraqqiyotga qaramasdan, NP-to'liq qarorida orqa ryukzak vazifalari, haqiqiy hayotdan olingan bunday o'lchamlarning aksariyatini hal qilish muammo bo'lib qolmoqda. [8 va 9] asosiy usullarini ta'riflaydi, turli vazifa variantlari uchun ishlatiladi Ryukzak muammosi 1-rasm ryukzak muammosi. Bir o'lchovli ( cheklovli ) ryukzak muammosining misoli: umumiy og'irlikni 15 kg gacha yoki unga teng ushlab turganda pul miqdorini maksimal darajada oshirish uchun qaysi qutilarni tanlash kerak? A bir nechta cheklangan muammo qutilarning vaznini ham, hajmini ham ko'rib chiqishi mumkin. (Qaror: agar har bir qutining biron bir raqami mavjud bo'lsa, unda uchta sariq quti va uchta kulrang quti; agar ko'rsatilgan qutilar mavjud bo'lsa, unda yashil qutidan tashqari barchasi.) Keling, KS () funktsiyasi bilan amalga oshiriladigan algoritmga va orqa ryukzak uchun ob'ektlarning ketma-ketligini shakllantirish dinamikasiga qisqacha to'xtalamiz. Rekursiya j - tartib raqami (noldan va undan keyin) bilan tartibga solinadi (rasmga qarang).8). J chuqurligining har bir chaqiruvida i-element (i, j = 0, 1, ..., m-1) hisobiga qisman yechimni kengaytirishga urinish amalga oshiriladi. Shu bilan birga, i parametri noldan va undan keyin birlikka teng bo'lgan qadam bilan o'zgaradi, qisman yechimni kengaytirish uchun ruxsat etilgan ob'ektning eng

kichik sonining qiymatini olishga harakat qiladi. Har qanday oldingi recursive chaqiruviga o'tishda i parametri joriy darajadagi qiymatdan birlikka teng qadam bilan o'zgarishni davom ettiradi, shuningdek qisman yechimni kengaytirish uchun ruxsat etilgan ob'ektning eng kichik raqamini olishga harakat qiladi. Agar hozirgi rekursiv chaqiruvda qurilgan qisman qaror endi o'zgartirilmasa, avvalgi chaqiruvga qaytish bo'ladi. J=0 darajasidan qaytib kelganda, hisob-kitoblar to'xtatiladi, ammo bu vaqtga kelib, muammoni hal qilish allaqachon olingan va ot vektorida joylashgan. KS() funktsiyasini qo'shimcha parametri bilan ta'minlasangiz va uni takroriy chaqiruvlarda quyidagi tarzda ishlatsangiz, hisob-kitoblarning sezilarli tezlashishiga erishish mumkin. Ks ga dastlabki murojaat qilinganda () = 0 ni hisoblang. Bundan tashqari, agar qisman yechimga ba'zi rekursiv chaqiruvlar i mavzusiga kiritilgan bo'lsa, keyingi recursiv darajaga o'tishda sizni qo'yishingiz kerak. Bu qisman yechimni yanada kengaytirishga harakat qilganda, bu qiymat (nol emas) va ob'ektning boshlang'ich raqami sifatida ishlatiladi. Shuni esda tutingki, bu holda pos belgilarining vektori mutlaqo keraksiz bo'lib qoladi, unda ob'ektlarning qisman yechimiga ulangan raqamlar ilgari qayd etilgan. Ryukzak muammosi kombinatorial optimallashtirish : Har birining vazni va qiymati bo'lgan buyumlar to'plamini hisobga olgan holda, jami og'irlik berilgan chegaradan kichik yoki unga teng bo'lgan va umumiy qiymati iloji boricha katta bo'lishi uchun to'plamga kiritiladigan har bir narsaning sonini aniqlang. Bu o'z nomini belgilangan o'lcham bilan cheklangan kishi duch keladigan muammodan kelib chiqadi ryukzak va uni eng qimmatbaho buyumlar bilan to'ldirishi kerak. Muammo ko'pincha paydo bo'ladi resurslarni taqsimlash bu erda qaror qabul qiluvchilar ajratilgan byudjet yoki vaqt cheklovi bo'yicha bo'linmaydigan loyihalar yoki vazifalar to'plamini tanlashlari kerak. 1999 yil Stoni Bruk universiteti algoritmi omborini o'rganish natijasida 75 ta algoritmik masaladan ryukzak muammosi eng ommabop 19-o'rin va eng zarur