Reppu ongelma

Reppuongelma (myös reppuongelma ) on NP-täydellinen kombinatorinen optimointiongelma . Se on saanut nimensä lopullisesta tavoitteesta: laittaa reppuun mahdollisimman paljon arvokasta tavaraa, mikäli repun kapasiteetti on rajallinen. Reppuongelmasta voi kohdata erilaisia muunnelmia taloustieteessä , sovelletussa matematiikassa , kryptografiassa ja logistiikassa .

Yleisesti ottaen ongelma voidaan muotoilla seuraavasti: annetusta kohteiden joukosta , joilla on ominaisuudet "kustannus" ja "paino", on valittava osajoukko , jolla on enimmäiskokonaiskustannukset, samalla kun otetaan huomioon kokonaispainon rajoitus.

Klassinen ongelman ilmaus

Olkoon joukko objekteja, joilla jokaisella on kaksi parametria - massa ja arvo. Siellä on myös reppu, jolla on tietty kantavuus. Tehtävänä on rakentaa reppu, jonka sisällä olevien esineiden enimmäisarvo on reppujen kokonaismassarajaa kunnioittaen.

Matemaattisesti ongelma on muotoiltu seuraavasti: rahtia on. Jokaista kuormaa varten määritetään sen massa ja arvo . Reppussa olevien tavaroiden kokonaispainon rajan määrää kantokyky . Välttämätön $n$ $i$ $w_{i}>0$ $v_{i}>0$ $i=1,2,...,n$ $W$

maksimoida

{\displaystyle \sum _{i=1}^{n}v_{i}x_{i))

rajoituksin ja [1] .

\sum _{i=1}^{n}w_{i}x_{i}\leq W

x_{i}\in \{0,1\}

Reppuongelman muunnelmia

Ongelmanselvitys sallii suuren määrän yleistyksiä, riippuen reppulle, esineille tai niiden valinnasta asetetuista ehdoista. Suosituimmat lajikkeet ovat seuraavat:

Reppu 0-1 ( eng. 0-1 Reppuongelma ) [2] : enintään yksi kopio jokaisesta esineestä.
Rajoitettu reppuongelma [3] : enintään tietty määrä kunkin kohteen esiintymiä.
Rajoittamaton selkäreppuongelma [3] : Satunnainen määrä esiintymiä jokaisesta esineestä.
Monivalintareppuongelma [ 4] : Tuotteet on jaettu ryhmiin, ja kustakin ryhmästä on valittava vain yksi esine.
Useiden reppujen ongelma [5] : On olemassa useita reppuja, joista jokaisella on oma enimmäispainonsa. Jokainen esine voidaan laittaa mihin tahansa reppuun tai jättää.
Moniulotteinen reppuongelma : painon sijaan annetaan useita erilaisia resursseja (esimerkiksi paino, tilavuus ja pinoamisaika). Jokainen tuote käyttää tietyn määrän jokaista resurssia. Kohteiden osajoukko on valittava siten, että kunkin resurssin kokonaiskustannus ei ylitä tämän resurssin maksimiarvoa ja samalla kohteiden kokonaisarvo on maksimi [4] .
Kvadraattinen reppuongelma : kokonaisarvo saadaan ei-negatiivisella määrätyllä neliömuodolla [6] .

Epälineaarinen reppuongelma

Yksi reppuongelman yleisimmistä muunnelmista on epälineaarinen . Se voidaan muotoilla seuraavasti:

Anna vektorin määrittää kunkin repun esineen esiintymien lukumäärä. Sitten ongelmana on löytää funktion minimi ${\displaystyle x=(x_{1},..,x_{n})\in \mathbb {R} ^{n))$

${\näyttötyyli \min _{x\in S}\ f(x)}$ ,

tietyllä rajoituksella:

$g(x)\leq b$ .

Funktioiden oletetaan olevan jatkuvia ja differentioituvia . on kokonaislukuvakio , joukko ei ole tyhjä [7] . $f(x),g(x):\mathbb {R} ^{n}\rightarrow \mathbb {R}$ $\mathbb {R} ^{n}$ $b$ $S$

Lineaaristen funktioiden tapauksessa ongelma rajoittuu johonkin klassisista formulaatioista riippuen joukosta : $f(x),g(x)$ $S$

${\displaystyle S=\{0,1\}^{n))$ - reppu 0-1
$S=\mathbb {N_{0}} ^{n}$ - rajoittamaton reppu
$S=\{(x_{1},..,x_{n})\in \mathbb {N_{0}} ^{n}:x_{i}\leq c_{i}\}$ - rajoitettu reppu

Vapaus toimintojen valinnassa mahdollistaa laajemman luokan tehtävien ratkaisemisen, mukaan lukien tuotantolaitosten organisoinnin $f(x),g(x)$ , näytteiden optimaalinen jakautuminen alueellisessa otoksessa tai neliöllisen reppuongelman ratkaisu [7] .

Tarkat ratkaisumenetelmät

Kuten edellä mainittiin, reppuongelma kuuluu luokkaan NP-complete , eikä sille ole toistaiseksi löydetty polynomialgoritmia , joka ratkaisee sen kohtuullisessa ajassa. Siksi reppuongelmaa ratkaistaessa on valittava tarkkojen algoritmien välillä, jotka eivät sovellu "suuriin" reppuihin, ja likimääräisistä algoritmeista, jotka toimivat nopeasti, mutta eivät takaa optimaalista ongelman ratkaisua.

Täysi luettelo

Kuten muutkin erilliset ongelmat , reppuongelma voidaan ratkaista luettelemalla tyhjentävästi kaikki mahdolliset ratkaisut.

Ongelman tilanteen mukaan on esineitä, jotka voidaan laittaa reppuun, ja sinun on määritettävä kuorman enimmäishinta, jonka paino ei ylitä . $N$ $W$

Jokaiselle tuotteelle on 2 vaihtoehtoa: tavara laitetaan reppuun tai esinettä ei sijoiteta reppuun. Tällöin kaikkien mahdollisten vaihtoehtojen luettelointi on ajallisesti monimutkainen , mikä mahdollistaa sen käytön vain pienelle määrälle kohteita [8] . Kohteiden määrän kasvaessa ongelma tulee ratkeamattomaksi tällä menetelmällä hyväksyttävässä ajassa. $O(2^{N})$

Kuvassa on iteraatiopuu kolmelle alkiolle. Jokainen lehti vastaa jotakin esineiden alajoukkoa. Puun kokoamisen jälkeen on löydettävä lehti, jolla on suurin arvo niiden joukosta, joiden paino ei ylitä [9] . $W$

Branch and Bound Method

Haara ja sidottu menetelmä on muunnelma raakavoiman menetelmästä sillä erolla, että raa'an voiman puun tietoisesti epäoptimaaliset oksat jätetään pois. Kuten raa'an voiman menetelmä, sen avulla voit löytää optimaalisen ratkaisun ja kuuluu siksi täsmällisiin algoritmeihin.

Alkuperäinen Peter Kolesarin vuonna 1967 ehdottama algoritmi ehdottaa kohteiden lajittelua niiden yksikkökustannusten (arvon ja painon suhteen) mukaan ja raa'an voiman puun rakentamista . Sen parannus on siinä, että jokaiselle solmulle rakennettaessa puuta estimoidaan ratkaisun arvon yläraja ja puun rakentaminen jatkuu vain maksimiestimaatin solmun kohdalla [10] . Kun suurin yläraja on puun lehdellä, algoritmi lopettaa työnsä.

Haara- ja sidotun kyky vähentää iteraatioiden määrää riippuu suuresti syöttötiedoista. On suositeltavaa käyttää sitä vain, jos kohteiden erityisarvot eroavat merkittävästi [11] .

Dynaamiset ohjelmointimenetelmät

Rajoittamaton reppuongelma

Esineiden painojen lisärajoituksella selkäreppuongelma voidaan ratkaista pseudopolynomiaalisessa ajassa dynaamisilla ohjelmointimenetelmillä .

Olkoon kunkin kohteen paino positiivinen kokonaisluku. Sitten ongelman ratkaisemiseksi on tarpeen laskea optimaaliset ratkaisut kaikille , missä on annettu kantavuus. Määritellään tavaroiden enimmäisarvo, joka voidaan sijoittaa reppuun, jonka kantavuus on . $w_{i}$ $w\in \mathbb {Z} :0\leq w\leq W$ $W$ $m[w]$ $w$

Sillä voit kirjoittaa rekursiivisia kaavoja : $m[w]$

$m[0]=0$
$m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])$ [12] ,

missä ovat vastaavasti -:nnen kohteen arvo ja paino , ja tyhjän joukon maksimiarvo on katsottava nollaksi. $v_{i},w_{i}$ $i$

Itse asiassa viimeinen yhtälö on R. Bellmanin funktionaalinen yhtälö tai dynaamisen ohjelmoinnin funktionaalinen yhtälö. Tässä tapauksessa sen ratkaisemiseksi riittää laskea kaikki arvot alkaen [12] ja asti . Jos tallennamme jokaiseen vaiheeseen lisäksi joukon kohteita, jotka toteuttavat maksimiarvon, niin algoritmi antaa myös optimaalisen kohteiden joukon. $m[w]$ $0$ $W$

Koska jokaisessa vaiheessa on tarpeen löytää alkioiden maksimi , algoritmin laskennallinen monimutkaisuus on . Koska se voi riippua eksponentiaalisesti syötteen koosta, algoritmi on pseudopolynomiaalinen . Siksi tämän algoritmin tehokkuus määräytyy arvon . Algoritmi antaa erinomaiset tulokset kohteelle , mutta ei kovin hyviä [13] . $n$ $O(nW)$ $W$ $W$ $W\leq 1000$ $W\geq 10\000\000$

Reppuongelma 0-1

0-1 reppuongelman ratkaisu on lähellä edellisen tehtävän ratkaisua, mutta on otettava huomioon, että jokainen esine on yhtenä kappaleena. Antaa olla ensimmäisistä saatavilla olevista kohteista saatujen tavaroiden enimmäisarvo , joiden kokonaispaino on enintään . $m[i,w]$ $i$ $w$

Toistuvat suhteet :

$m[0,w]=0$
$m[i,\,w]=m[i-1,\,w]$ , jos $w_{i}>w$
$m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ , jos $w_{i}\leq w$

Laskemalla voit löytää tarkan ratkaisun. Jos matriisi mahtuu koneen muistiin, tämä algoritmi on luultavasti yksi tehokkaimmista [12] . $m[n,W]$ $m[i,w]$

// Syöte: // Nimikkeiden arvot (ladattu taulukkoon v) // Nimikkeiden painot (ladataan taulukkoon w) // Tavaroiden lukumäärä (n) // Kantavuus (W) j : lle 0 - W tee : m [ 0 , j ] := 0 minulle 1 - n tehdä : _ _ j : lle 0 - W tee : jos w [ i ] > j niin : m [ i , j ] : = m [ i - 1 , j ] muuta : m [ i , j ] := max ( m [ i -1 , j ], m [ i -1 , j - w [ i ]] + v [ i ])

Ratkaisu voidaan havainnollistaa dynaamisella ohjelmoinnilla seuraavasti: kaksiulotteisessa tasossa objektien lukumäärä piirretään akselille ja niiden paino akselille. Ensimmäisessä vaiheessa rakennetaan kaksi viivaa koordinaattien origosta: vaakasuuntainen, joka vastaa sitä tosiasiaa, että ensimmäistä objektia ei otettu, ja kalteva, joka vastaa ensimmäistä otettua objektia. Niiden projektiot akselilla ovat yhtä suuret kuin kohteen paino. Toisessa vaiheessa rakennetaan jälleen 2 viivaa, vaakasuora (toinen kohde ei otettu) tai vino (toinen kohde otettiin). Asetetaan vaakakaarien pituudeksi nolla ja vinojen kaarien pituudeksi kohteen arvo [14] . Siten mikä tahansa ongelman ratkaisu vastaa jotakin polkua rakennetussa puussa . Ongelma rajoittuu maksimipituisen polun löytämiseen [14] . Anna kapasiteettireppu . $X$ $Y$ $Y$ $W=14$

Tuotenumero	Arvo	Paino
yksi	3	5
2	5	kymmenen
3	neljä	6
neljä	2	5

Kuvasta voidaan nähdä, että optimaalisen ratkaisun kokonaisarvo on 7, koska tämä on rakennetun puun maksimiarvo.

Dynaaminen ohjelmointi nimikkeiden arvojen yli

Toistuvuussuhteet voidaan kirjoittaa paitsi esineiden painon, myös arvon suhteen. Tätä varten merkitsemme kohteiden vähimmäispainoa kokonaisarvolla , joka voidaan saada ensimmäisistä kohteista. Jos vaadittua painoa ei saada, merkitse se muodossa . ${\näyttötyyli y[i,V]}$ $V$ $i$ $y[i,V]=W+1$

Sen jälkeen ratkaisemme toiminnallisen dynaamisen ohjelmoinnin yhtälön :

$y[i,V]={\begin{cases}y[i-1,V],&{\text{if }}V<v_{i}\\\min\{\ y[i- 1,V],y[i-1,V-v_{i}]+w_{i}\},&{\text{if }}V\geq v_{i}\end{cases}}$ ,

alkuehdoilla : _

$y[0,0]=0$

$y[0,V]=W+1$ [viisitoista]

Likimääräiset ratkaisumenetelmät

Kuten useimmissa NP-täydellisissä ongelmissa, ei aina tarvitse saada tarkkaa ratkaisua, koska optimaalisen lähellä olevia ratkaisuja voidaan soveltaa sovellettaviin ongelmiin.

Ahne algoritmi

Ongelman ratkaisemiseksi ahneella algoritmilla on tarpeen lajitella asiat niiden tietyn arvon mukaan (eli tavaran arvon ja sen painon suhteen) ja sijoittaa reppuun tavarat, joilla on suurin ominaisarvo [10] .

Tämän algoritmin ajoaika on lajitteluajan ja pinoamisajan summa. Kohteiden lajittelun monimutkaisuus on . Seuraavaksi se laskee kuinka monta esinettä mahtuu reppuun kokonaisajassa [10] . Tuloksena oleva monimutkaisuus , kun lajittelua tarvitaan ja kun tiedot on jo lajiteltu [10] . $O(N\log(N))$ $O(N)$ $O(N\log(N))$ $O(N)$

Esimerkki . Anna kapasiteettireppu . Tuotteet on jo lajiteltu yksikön arvon mukaan. Käytetään ahneita algoritmeja. $W=80$

i	paino	hinta	hinta/paino
yksi	viisitoista	60	neljä
2	kolmekymmentä	90	3
3	viisikymmentä	100	2

Laitoimme ensimmäisen esineen reppuun ja sen jälkeen toisen. Kolmas esine ei mahdu reppuun. Repun tavaroiden yhteisarvo on 150. Jos toinen ja kolmas esine otettaisiin, kokonaisarvo olisi 190. Siten olemme saaneet jonkinlaisen ei-optimaalisen ratkaisun.

On ymmärrettävä, että ahne algoritmi voi johtaa vastaukseen, joka on mielivaltaisen kaukana optimaalisesta. Jos esimerkiksi yhden kohteen paino on 1 ja hinta 2 ja toisen paino on W ja hinta W, ahne algoritmi saa kokonaishinnaksi 2, kun optimaalinen vastaus on W. samaan aikaan sama algoritmi rajoittamattomalle reppu-ongelmalle johtaa vastaukseen, joka on vähintään 50 % optimaalisen arvosta [10] .

George Danzig [16] ehdotti ensimmäisenä ahnetta algoritmia rajoittamattoman selkäreppu-ongelman ratkaisemiseksi.

Likimääräinen kaavio täysin polynomiselle ajalle

Koska tarkkaa algoritmia ongelman ratkaisemiseksi polynomiajassa ei löytynyt, syntyi ongelma saada polynomiratkaisu taatulla tarkkuudella . Tätä varten on olemassa useita likimääräisiä kaavioita täysin polynomisesta ajasta , eli joiden monimutkaisuus on polynomi ja . $1-\varepsilon$ $n$ ${\frac {1}{\varepsilon }}$

Klassisen mallin ideana on vähentää tarkkuusarvojen antamista. Yhdistämällä samanarvoisia kohteita yhdeksi ryhmäksi voit vähentää eri kohteiden määrää. Algoritmi kirjoitetaan seuraavasti [15] :

Etsitään likimääräinen ratkaisu ahneella algoritmilla. Olkoon oikea ratkaisu. Sitten ahneen algoritmin tehokkuusarviosta . ${\näyttötyyli x^{l))$ $x^{*}$ ${\displaystyle x^{l}\leq x^{*}\leq 2x^{l))$
Skaalaa arvot seuraavasti: . $v'_{i}=\left\lfloor {\frac {v_{i}}{\frac {x^{l}\varepsilon }{n}}}\right\rfloor$
Käyttämällä dynaamista ohjelmointialgoritmia objektien kokonaislukuarvojen ongelmaan löydämme ratkaisun.

On olemassa monia erilaisia approksimaatiomalleja. Ne riippuvat kuitenkin voimakkaasti reppuongelman muotoilusta. Jos esimerkiksi toinen epäyhtälötyyppinen rajoite (kaksiulotteinen selkäreppu) esiintyy ehdossa, ongelmalla ei ole enää tunnettua polynomiaikakaaviota [17] .

Geneettiset algoritmit

Kuten muissakin NP-kovissa optimointiongelmissa, reppuongelman ratkaisemiseen käytetään geneettisiä algoritmeja . Ne eivät takaa optimaalisen ratkaisun löytämistä polynomiajassa eivätkä anna arviota ratkaisun läheisyydestä optimaaliseen, mutta niillä on hyvät aikaindikaattorit, joiden avulla voit löytää melko hyvän ratkaisun nopeammin kuin muut tunnetut deterministiset tai heuristiset menetelmiä. [kahdeksantoista]

Jokainen yksilö ( genotyyppi ) on osa tavaroista, jotka haluamme pakata laukkuun (niiden kokonaispaino voi ylittää sallitun kantokyvyn). Mukavuussyistä tiedot tallennetaan binäärisinä merkkijonoina, joissa jokainen bitti määrittää, mahtuuko tämä kohde laukkuun [19] .

Kuntotoiminto määrittää ratkaisun läheisyyden optimaaliseen ratkaisuun. Esimerkiksi tavaroiden kokonaisarvo voi toimia sellaisena, mikäli kokonaispaino ei ylitä kantokykyä.

Sukupolvenvaihdosten sarjan jälkeen, joissa vahvimmat yksilöt risteytetään ja loput jätetään huomiotta, algoritmin oletetaan parantavan alkuperäisiä ratkaisuja [19] .

Osajoukon summaongelman ratkaiseminen

Reppu 0-1 - tehtävän erikoistapaus on osajoukon summa - tehtävä . Olkoon reppun kantokyky, olkoon -:nnen esineen paino ja sen hinta . Tehtävänä on siis ladata reppu mahdollisimman tiukasti tai kuluttaa resurssit kokonaan pois: $W$ $w_{i}$ $i$ $v_{i}=w_{i}$

$W=\sum _{i=1}^{N}w_{i}x_{i},\qquad \ x_{i}\in \{0,1\}$

Sen ratkaisemiseksi voit käyttää mainittua geneettistä algoritmia . Yksilö on vektori . Kuntotoimintona tulisi käyttää esineiden kokonaispainon läheisyyttä kohtaan , ainoana ominaisuutena on, että reppuun mahtuvat sarjat ovat parempia (esineiden kokonaispaino on pienempi kuin ) [19] . ${\näyttötyyli (x_{1},...,x_{n})}$ $W$ $W$

Määritelkäämme muodollisesti kuntofunktio . Antaa olla kaikkien kohteiden painojen summa. Sitten - repussa olevien esineiden painon suurin mahdollinen poikkeama . $f(x_{1},..,x_{n}):\{0,1\}^{n}\rightarrow \mathbb {R}$ $\mathcal{S}$ ${\textstyle \Delta _{max}=max(W,{\mathcal {S}}-W)}$ $W$

Antaa olla kohteen kokonaispaino tietylle vektorille. Sitten laitamme: ${\textstyle W'=\sum _{i=1}^{N}w_{i}x_{i}}$

$f(x_{1},..,x_{n})={\begin{cases}1-{\sqrt {\frac {WW'}{W))},&W'\leq W,\ \1-{\sqrt {\frac {W'-W}{\Delta _{max)))),&W'>W.\end{cases))$ [19]

Yleisen algoritmin avulla voimme löytää likimääräisen ratkaisun:

Luo satunnainen joukko yksilöitä - populaatio.
Laske mukautusfunktio kullekin yksilölle.
Jätä vain vahvimmat yksilöt (luonnollinen valinta).
Suorita risteyksiä.
mutatoitua jälkeläisiä.
Jatka toisesta vaiheesta.

Suoritus keskeytyy joko ratkaisun löytyessä tai tietyn iteraatiomäärän jälkeen [19] .

Sovellukset

Ei tiedetä varmasti, kuka ensimmäisenä antoi reppuongelman matemaattisen muotoilun. Yksi ensimmäisistä viittauksista siihen löytyy George Ballard Matthewsin artikkelista[20] [21] päivätty 1897. Tämän ongelman intensiivinen tutkimus alkoi sen jälkeen , kun D. B. Dantzig julkaisi vuonna 1957 kirjan “ Englanti. Discrete Variable Extreum Problem » [22] , erityisesti 1900-luvun 70-90-luvuilla, sekä teoreetikot että harjoittajat [2] . Kiinnostuksen aiheutti monella tapaa ongelman melko yksinkertainen muotoilu, suuri määrä sen lajikkeita ja ominaisuuksia sekä samalla niiden ratkaisun monimutkaisuus. Vuonna 1972 tämä ongelma sisällytettiin M. Karpin NP-täydellisten ongelmien luetteloon ( englanninkielinen artikkeli "Reducibility among Combinatorial Problems" ) [23] .

Reppuongelman visuaalinen tulkinta on johtanut siihen, että sille on löydetty käyttöä useilla tiedon aloilla: matematiikassa, tietojenkäsittelytieteessä ja näiden tieteiden risteyksessä kryptografiassa . Yhdessä laskennallista lingvistiikkaa käsittelevässä teoksessa [24] ehdotetaan tekstien automaattisen yhteenvedon ongelman muotoilua , jonka erikoistapaus vastaa reppuongelman muotoilua.

Selkäreppuongelman perusteella luotiin ensimmäinen epäsymmetrinen salausalgoritmi . Whitfield Diffie ja Martin Hellman esittelivät idean julkisen avaimen salauksesta ensimmäisen kerran vuoden 1976 kansallisessa tietokonekonferenssissa [25] [26] .

Myös reppuongelma voi toimia mallina useille teollisille ongelmille [2] [27] :

Tavaroiden sijoittaminen varastoon, jonka pinta-ala on pieni.
Kankaan leikkaus - hanki olemassa olevasta materiaalikappaleesta enimmäismäärä tietyn muotoisia kuvioita.
Optimaalisten pääomasijoitusten laskeminen .

Reppu-ongelma kryptografiassa

Vuonna 1978 Ralph Merkle ja Martin Hellman kehittivät ensimmäisen algoritmin yleiselle julkisen avaimen salaukselle , Merkle-Hellmanin salausjärjestelmän , joka perustuu reppuongelmaan. He julkaisivat yksivaiheisia ( englanniksi singly-iterated ) ja monivaiheisia ( englanninkielisiä multiply-iterated ) versioita, ja algoritmia voitiin käyttää vain salaukseen. Mutta Adi Shamir mukautti sen käytettäväksi digitaalisissa allekirjoituksissa [28] .

Myöhemmin ehdotettiin muita selkäreppuongelmaan perustuvia salausjärjestelmiä, joista osa on muunnelmia Merkle-Hellmanin kryptosysteemistä. Tunnetut kryptojärjestelmät [29] :

Grahamin reppu - Shamira
Goodmanin reppu - Macauley
Nakkasha reppu - Stern
Shorin reppu - Rivesta

Salaus selkäreppu-ongelman kanssa

Koska yleistä reppuongelmaa ei voida ratkaista täsmälleen kohtuullisessa ajassa, sitä voidaan käyttää kryptografisissa ongelmissa. Tätä varten esitämme viestin julkisesti tunnetuilla kohteilla lähetettyjen kohteiden joukkona ja lähetämme niiden kokonaispainon [28] .

Määritelmä. Reppuvektori on n:n esineen järjestetty joukko, jossa on -: nnen esineen paino [30] . $A=(a_{1},...,a_{n})$ $a_i$ $i$

Reppuvektori on julkinen avain . Selkeän tekstin salaamiseksi se jaetaan bitin pituisiin lohkoihin, jolloin jokainen bitti määrittää esineen läsnäolon repussa (esimerkiksi selväteksti vastaa neljän ensimmäisen kuudesta mahdollisesta esineestä repussa). Uskotaan, että yksi ilmaisee esineen läsnäolon repussa ja nolla sen puuttumista [28] . $n$ $(111100)$

Tämän jälkeen lasketaan reppussa olevien tavaroiden kokonaispaino annetulle selväkieliselle tekstille ja lähetetään salatekstinä [28] .

Esimerkki salauksesta tällä algoritmilla:

Olkoon reppuvektori , jonka pituus on annettu . $A=(3\ 4\ 6\ 7\ 10\ 11)$ $n = 6$

pelkkää tekstiä	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0 0	0 0 0 0 0 1
Tavarat repussa	3 4 6 7 10	6 7		yksitoista
Salateksti	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	yksitoista

Muistiinpanot

↑ Silvano, 1990 , s. yksi.
↑ 1 2 3 Silvano, 1990 , s. 2.
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 , s. 127.
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 , s. 147.
↑ Silvano, 1990 , s. 157.
↑ G. Gallo, P. L. Hammer, B. Simeone. Quadratic knapsack -ongelmat // Mathematical Programming Studies. - 2009. - 24. helmikuuta ( osa 12 ). - s. 132-149 . — ISSN 0303-3929 . Arkistoitu alkuperäisestä 24. lokakuuta 2016.
↑ 1 2 Brettauer, Shetty, 2002 .
↑ Okulov, 2007 , s. 92-93.
↑ Okulov, 2007 , s. 101-105.
↑ 1 2 3 4 5 Martello S., Toth P. Reppuongelmat: algoritmit ja tietokonetoteutukset . - John Wiley & Sons Ltd., 1990. - S. 29,50 . — 296 s. — ISBN 0-471-92420-2 .
↑ Burkov, Gorgidze, Lovetsky, 1974 , s. 225.
↑ 1 2 3 Romanovsky I.V. Algoritmit äärimmäisten ongelmien ratkaisemiseksi . - Nauka, 1977. - S. 252 -259. — 352 s.
↑ Stephen S. Skiena. Algoritmit. Kehittämisopas. - 2. - Pietari. : BHV-Petersburg, 2011. - S. 448-451. – 720 s. - ISBN 978-5-9775-0560-4 .
↑ 1 2 Novikov, 2001 , s. 12.
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 .
↑ Dantzig G. B. Discrete-Variable Extreum Problems // Oper . Res. - Operaatiotutkimuksen ja johtamistieteiden laitos , 1957. - Voi. 5, Iss. 2. - s. 266-288. - klo 23 — ISSN 0030-364X ; 1526-5463 - doi:10.1287/OPRE.5.2.266
↑ Ariel Kulik, Hadas Shachnai. Kaksiulotteiselle selkärepulle ei ole olemassa EPTAS:a // Information Processing Letters. – 31.7.2010. - T. 110 , no. 16 . — S. 707–710 . - doi : 10.1016/j.ipl.2010.05.031 .
↑ D.I. Batishchev, E.A. Neimark, N.V. Starostin. Geneettisten algoritmien soveltaminen diskreettien optimointiongelmien ratkaisemiseen . - 2007. - Nižni Novgorod. Arkistoitu 22. helmikuuta 2016 Wayback Machineen
↑ 1 2 3 4 5 S. M. Avdoshin, A. A. Saveljeva. Salausanalyysi: nykytila ja kehitysnäkymät . - S. 38 . Arkistoitu alkuperäisestä 17. maaliskuuta 2016. (Venäjän kieli)
↑ G.B. Mathews. Numeroiden jaosta (englanniksi) . - 1897. - s. 486-490.
↑ Kellerer, Pferschy, Pisinger, 2004 , s. 3.
↑ Kellerer, Pferschy, Pisinger, 2004 , s. 9.
↑ R. Karp. Vähennettävyys kombinatoristen ongelmien joukossa . – 1972.
↑ Riedhammer et al, 2008 , s. 2436.
↑ Schnaer, 2002 , s. 19.2.
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ Burkov, Gorgidze, Lovetsky, 1974 , s. 217.
↑ 1 2 3 4 Schnaer, 2002 , s. 19.1.
↑ Kin Ming Lai. Knapsack Cryptosystems: Menneisyys ja tulevaisuus . – 2001. (Venäjän kieli)
↑ Salomaa, 1995 , s. 103.

Kirjallisuus

venäjäksi

Levitin A. V. Algoritmit. Johdatus kehitykseen ja analyysiin - M . : Williams , 2006. - S. 160-163. — 576 s. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmit: rakentaminen ja analyysi = Algoritmien johdatus. - 2. - M . : "Williams" , 2006. - S. 456-458. — ISBN 0-07-013151-1 .
Robert Sedgwick . Perusalgoritmit C++:ssa. Osat 1-4. Analyysi. Tietorakenteet. Lajittelu. Haku = Algoritmit C++:ssa. Osat 1-4. perusasiat. Tietorakenteet. Lajittelu. Etsitään. - 3. - Venäjä, Pietari: "DiaSoft" , 2002. - S. 688. - ISBN 5-93772-047-4 , 0-201-35088-2.
Burkov V. N. , Gorgidze I. A. , Lovetsky S. E. Graafiteorian sovelletut ongelmat / toim. A. Ya. Gorgidze - Tbilisi : Neuvostoliiton tiedeakatemian laskentakeskus , 1974. - 231 s.
V. N. Burkov, D. A. Novikov. Graafiteorian elementit . - 2001. - S. 28.
S. Okulov. Ohjelmointi algoritmeissa . - 1. — Binom. Knowledge Laboratory, 2007. - S. 384. - ISBN 5-94774-010-9 .
B. Schneier. Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodit C. - 2nd. - Triumph, 2002. - 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 . Arkistoitu 18. joulukuuta 2018 Wayback Machineen
A. Salomaa. Julkisen avaimen salaus = Public-Key Cryptography . - M .: Mir, 1995. - S. 102-150. - ISBN 5-03-001991-X. Arkistoitu 4. maaliskuuta 2016 Wayback Machinessa
N. Koblitz. Numeroteorian kurssi kryptografiassa. - 2. - M . : TVP Scientific Publishing House, 2001. - S. 254. - ISBN 5-85484-014-6 .
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Tietoturva : oppikirja - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
Osipyan V. O. Reppuongelmaan perustuvasta tietoturvajärjestelmästä // Tomskin ammattikorkeakoulun tiedote [TPU Bulletin]. - 2006. - T. 309 , nro 2 . - S. 209-212 .

englanniksi

Silvano Martelo, Paolo Toth. Reppu-ongelmat . - Iso-Britannia: Wiley, 1990. - 306 s. — ISBN 0-471-92420-2 .
Kellerer H. , Pferschy U. , Pisinger D. Knapsack Problems (englanniksi) - Springer Science + Business Media , 2004. - 548 s. - ISBN 978-3-642-07311-3 - doi:10.1007/978-3-540-24777-7
K. Riedhammer, D. Gillick, B. Favre ja D. Hakkani-Tür. Kokouksen yhteenvetorepun pakkaaminen . — Brisbane Australia: Proc. Interspeech, Brisbane, Australia, 2008.
Brettauer K. M. , Shetty B. Epälineaarinen selkäreppuongelma – algoritmit ja sovellukset (englanniksi) // European Journal of Operational Research - Elsevier BV , 2002. - Voi. 138, Iss. 3. - s. 459-472. — ISSN 0377-2217 ; 1872-6860 - doi:10.1016/S0377-2217(01)00179-5

Linkit

Tervetuloa selkäreppuun
Reppuongelma Eric Grimsom John Guttag - MIT
Selkäreppu-ongelmien ratkaisuja monilla kielillä
Das Rucksack-Problem (reppuongelma) (saksa)

Reppu-ongelma
Sovellukset	Reppu-ongelma kryptografiassa Leikkaustehtävä
Selkäreppuongelmaan perustuvat kryptojärjestelmät	Merkla-Hellman Naccasha - Stern Graham - Shamira
Lisäksi	Luettelo reppua koskevista tehtävistä

NP-täydellisiä ongelmia
Pinoamisen (pakkauksen) maksimointiongelma	Pakkaus säiliöihin kaksiulotteinen pakkaus lineaarinen pakkaus pakkaus painon mukaan pakkaus arvon mukaan Reppu ongelma
graafiteorian joukkoteoria	Vertex-kannen ongelma Napsauta ongelma Itsenäisen joukon (joukon) ongelma Aseta peittoongelma Steinerin ongelma Matkamyyjän ongelma Yleinen matkamyyjän ongelma
Algoritmiset ongelmat	Boolen kaavojen tyydyttävyysongelma (konjunktiivisessa normaalimuodossa)
Logiikkapelejä ja pulmia	Yleiset tunnisteet (peli N 2 -1:ssä) lyhin ratkaisu ongelma Ongelmat, joiden ratkaisuja käytetään Tetrisissä Yleistynyt Sudoku-ongelma Latinalaisen neliön täyttöongelma Kakuron tehtävä
Vaikeusluokat Toimintatutkimus Optimointi Kombinatorinen optimointi Sovellettu matematiikka Algoritmien teoria Dynaaminen ohjelmointi 21 NP-täydellinen Karp-ongelma