RYUKZAK MASALASI

Загружено в:

08.08.2023

Скачано:

0

Размер:

173.7490234375 KB

Скачать

“RYUKZAK MASALASI ” MAVZUSIDAGI
KURS ISHI
1

MUNDARIJA:
I bob. Kirish…………………………………….…………………………3
II bob. Nazariy qism………………………………………………………5
2.1. Ryukzak muammosi va Hisoblashning murakkabligi………………10
2.2. Hukmdorlik munosabatlari……………………………………….…11
2.3. Ryukzak vazifasi ……………………………………………………17
III bob. Xulosa…………………………………………………………...22
IV bob. Adabiyotlar……………………………………………………...23
2

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.
4

II bob .
2.1 . 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
5

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.
6

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]
7

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.
8

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
9

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.
10

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.
11

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]
12

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 .
13

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
14

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
15

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
16

$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. 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 17$

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
18

$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 19$

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.
20

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
21

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.
22

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. Ko'paytma va cheklangan masalalarni
sanab o'tish orqali hal qilinadi. Muammolarni yechishda 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, doimiy uchun qo'llash
mumkin emas ryukzak. Ochko'z algoritm bir mezonli, 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. Genetik algoritmning
yana bir kamchiligi shundaki, u kafolat bermaydi ba'zi vaziyatlarda optimal
yechimni topish. Bu algoritm mumkinligi bilan bog'liq optimal yechimga
erishilgandagina emas, balki quyidagi bilan ham yakunlanadi takrorlashning
belgilangan maksimal sonidan o'tgan; algoritmni bajarish uchun belgilangan
maksimal vaqt o'tdi; yangi avlodga o'tishda sezilarli o'zgarishlar sodir bo'lmaydi.
23

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. В. Н. Бурков, Д. А. Новиков. Элементы теории графов . — 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 .
24

10. Габидулин Э. М. , Кшевецкий А. С. , Колыбельников А. И. Защита
информации : учебное пособие — М.: МФТИ , 2011. — 225 с. — ISBN 978-
5-7417-0377-9
11. Осипян В. О. О системе защиты информации на основе проблемы
рюкзака // Известия Томского политехнического университета [Известия
ТПУ]. — 2006. — Т. 309 , № 2 . — С. 209-212 .
25

“RYUKZAK MASALASI ” MAVZUSIDAGI KURS ISHI 1

MUNDARIJA: I bob. Kirish…………………………………….…………………………3 II bob. Nazariy qism………………………………………………………5 2.1. Ryukzak muammosi va Hisoblashning murakkabligi………………10 2.2. Hukmdorlik munosabatlari……………………………………….…11 2.3. Ryukzak vazifasi ……………………………………………………17 III bob. Xulosa…………………………………………………………...22 IV bob. Adabiyotlar……………………………………………………...23 2

I bob.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. 3

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. 4

II bob . 2.1 . 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 5

RYUKZAK MASALASI

08.08.2023

0

173.7490234375 KB

Похожие