Tu je batoh ako nádoba alebo taška. Predpokladajme, že sme dali nejaké položky, ktoré majú nejakú váhu alebo zisk. Niektoré položky musíme vložiť do batohu tak, aby celková hodnota vyprodukovala maximálny zisk.

Napríklad hmotnosť nádoby je 20 kg. Položky musíme vyberať tak, aby súčet hmotnosti položiek bol buď menší alebo rovný hmotnosti kontajnera a zisk mal byť maximálny.

Existujú dva typy problémov s batohom:

• 0/1 problém s batohom
• Problém s frakčným batohom

Budeme diskutovať o oboch problémoch jeden po druhom. Najprv sa dozvieme o probléme s batohom 0/1.

Aký je problém s batohom 0/1?

Problém s batohom 0/1 znamená, že položky sú v batohu úplne alebo žiadne. Napríklad máme dve položky s hmotnosťou 2 kg a 3 kg. Ak vyberieme 2 kg položku, potom nemôžeme vybrať 1 kg položku z 2 kg položky (položka nie je deliteľná); 2kg tovar musíme vybrať úplne. Toto je problém s batohom 0/1, v ktorom buď vyberieme položku úplne, alebo vyberieme túto položku. Problém batohu 0/1 je vyriešený dynamickým programovaním.

Aký je problém s frakčným batohom?

Problém frakčného batohu znamená, že môžeme položku rozdeliť. Napríklad máme položku s hmotnosťou 3 kg, potom môžeme vybrať položku s hmotnosťou 2 kg a nechať položku s hmotnosťou 1 kg. Problém frakčného batohu je vyriešený prístupom Greedy.

Príklad problému s batohom 0/1.

Zvážte problém s váhami a ziskami:

Váhy: {3, 4, 6, 5}

Zisky: {2, 3, 1, 4}

Hmotnosť batohu je 8 kg

Počet kusov je 4

Vyššie uvedený problém je možné vyriešiť pomocou nasledujúcej metódy:

X_i= {1, 0, 0, 1}

= {0, 0, 0, 1}

javascript pre rozbaľovaciu ponuku

= {0, 1, 0, 1}

Vyššie uvedené sú možné kombinácie. 1 znamená, že položka je úplne vybratá a 0 znamená, že nie je vybratá žiadna položka. Keďže existujú 4 položky, možné kombinácie budú:

2⁴= 16; Takže. Existuje 16 možných kombinácií, ktoré možno vytvoriť pomocou vyššie uvedeného problému. Po vytvorení všetkých kombinácií musíme vybrať kombináciu, ktorá poskytuje maximálny zisk.

Ďalším prístupom k riešeniu problému je prístup dynamického programovania. V prístupe dynamického programovania je komplikovaný problém rozdelený na čiastkové problémy, potom nájdeme riešenie čiastkového problému a riešenie čiastkového problému sa použije na nájdenie riešenia zložitého problému.

Ako možno tento problém vyriešiť pomocou prístupu dynamického programovania?

Najprv,

vytvoríme maticu znázornenú nižšie:

Vo vyššie uvedenej matici predstavujú stĺpce váhu, t.j. 8. Riadky predstavujú zisky a váhy položiek. Tu sme nebrali priamo váhu 8, problém je rozdelený na podproblémy, t.j. 0, 1, 2, 3, 4, 5, 6, 7, 8. Riešenie podproblémov by bolo uložené v bunky a odpoveď na problém by sa uložila do poslednej bunky. Najprv zapíšeme váhy vo vzostupnom poradí a zisky podľa ich váh uvedených nižšie:

In_i= {3, 4, 5, 6}

p_i= {2, 3, 4, 1}

Prvý riadok a prvý stĺpec by boli 0, pretože pre w=0 neexistuje žiadna položka

Keď i=1, W=1

In₁= 3; Keďže v súprave máme iba jednu položku s hmotnosťou 3, ale kapacita batohu je 1. Nemôžeme naplniť položku 3 kg v batohu s kapacitou 1 kg, preto pridajte 0 na M[1][1] zobrazené nižšie :

Keď i = 1, W = 2

In₁= 3; Keďže v súprave máme iba jednu položku s hmotnosťou 3, ale kapacita batohu je 2. Nemôžeme naplniť položku 3 kg v batohu s kapacitou 2 kg, preto pridajte 0 pri M[1][2] znázornenom nižšie :

Keď i=1, W=3

In₁= 3; Keďže v súprave máme len jeden kus s hmotnosťou rovnajúcou sa 3 a hmotnosť batohu je tiež 3; preto môžeme batoh naplniť položkou s hmotnosťou rovnajúcou sa 3. Zisk zodpovedajúci hmotnosti 3, t.j. 2, dáme na M[1][3], ako je znázornené nižšie:

Keď i = 1, W = 4

_W1= 3; Keďže v súprave máme len jeden kus s hmotnosťou rovnajúcou sa 3 a hmotnosť batohu je 4; preto môžeme batoh naplniť položkou s hmotnosťou rovnajúcou sa 3. Zisk zodpovedajúci hmotnosti 3, t.j. 2, dáme na M[1][4], ako je znázornené nižšie:

Keď i = 1, W = 5

_W1= 3; Keďže v súprave máme len jeden kus s hmotnosťou rovnajúcou sa 3 a hmotnosť batohu je 5; preto môžeme batoh naplniť položkou s hmotnosťou rovnajúcou sa 3. Zisk zodpovedajúci hmotnosti 3, t.j. 2, dáme na M[1][5], ako je znázornené nižšie:

Keď i = 1, W = 6

_W1= 3; Keďže v súprave máme len jeden kus s hmotnosťou rovnajúcou sa 3 a hmotnosť batohu je 6; preto môžeme batoh naplniť položkou s hmotnosťou rovnajúcou sa 3. Zisk zodpovedajúci hmotnosti 3, t.j. 2, dáme na M[1][6], ako je znázornené nižšie:

Keď i = 1, W = 7

_W1= 3; Keďže v súprave máme len jeden kus s hmotnosťou rovnajúcou sa 3 a hmotnosť batohu je 7; preto môžeme batoh naplniť položkou s hmotnosťou rovnajúcou sa 3. Zisk zodpovedajúci hmotnosti 3, t.j. 2, dáme na M[1][7], ako je znázornené nižšie:

Keď i = 1, W = 8

_W1= 3; Keďže v súprave máme iba jeden kus s hmotnosťou rovnajúcou sa 3 a hmotnosť batohu je 8; preto môžeme batoh naplniť položkou s hmotnosťou rovnajúcou sa 3. Zisk zodpovedajúci hmotnosti 3, t.j. 2, dáme na M[1][8], ako je znázornené nižšie:

Teraz sa hodnota „i“ zvýši a stane sa 2.

Keď i = 2, W = 1

Hmotnosť zodpovedajúca hodnote 2 je 4, t.j. w₂= 4. Keďže v súprave máme len jeden predmet s hmotnosťou rovnajúcou sa 4 a hmotnosť batohu je 1. Predmet s hmotnosťou 4 nemôžeme vložiť do batohu, preto pripočítame 0 na M[2][1 ] zobrazené nižšie:

Keď i = 2, W = 2

Hmotnosť zodpovedajúca hodnote 2 je 4, t.j. w₂= 4. Keďže v súprave máme len jeden predmet s hmotnosťou rovnajúcou sa 4 a hmotnosť batohu je 2. Predmet s hmotnosťou 4 nemôžeme vložiť do batohu, preto pripočítame 0 na M[2][2 ] zobrazené nižšie:

Keď i = 2, W = 3

Hmotnosť zodpovedajúca hodnote 2 je 4, t.j. w₂= 4. Keďže máme v súprave dva predmety s hmotnosťou 3 a 4 a hmotnosť batohu je 3. Položku s hmotnosťou 3 môžeme vložiť do batohu, tak pridáme 2 na M[2][3] zobrazené ako nižšie:

Keď i = 2, W = 4

Hmotnosť zodpovedajúca hodnote 2 je 4, t.j. w₂= 4. Keďže máme v súprave dva predmety s hmotnosťou 3 a 4 a hmotnosť batohu je 4. Do batoha môžeme vložiť predmet s hmotnosťou 4, pretože zisk zodpovedajúci hmotnosti 4 je väčší ako predmet s hmotnosťou 3, takže pridáme 3 na M[2][4], ako je uvedené nižšie:

Keď i = 2, W = 5

Hmotnosť zodpovedajúca hodnote 2 je 4, t.j. w₂= 4. Keďže máme v súprave dva predmety s hmotnosťou 3 a 4 a hmotnosť batohu je 5. Do batoha môžeme vložiť predmet s hmotnosťou 4 a zisk zodpovedajúci hmotnosti je 3, tak pripočítame 3 pri M[2][5] zobrazené nižšie:

Keď i = 2, W = 6

Hmotnosť zodpovedajúca hodnote 2 je 4, t.j. w₂= 4. Keďže máme v súprave dva predmety s hmotnosťou 3 a 4 a hmotnosť batohu je 6. Do batoha môžeme vložiť predmet s hmotnosťou 4 a zisk zodpovedajúci hmotnosti je 3, tak pripočítame 3 pri M[2][6] zobrazené nižšie:

Keď i = 2, W = 7

Hmotnosť zodpovedajúca hodnote 2 je 4, t.j. w₂= 4. Keďže máme v súprave dva predmety s hmotnosťou 3 a 4 a hmotnosť batohu je 7. Do batohu môžeme vložiť predmet s hmotnosťou 4 a 3 a zisky zodpovedajúce hmotnostiam sú 2 a 3; preto je celkový zisk 5, takže pripočítame 5 na M[2][7], ako je uvedené nižšie:

Keď i = 2, W = 8

Hmotnosť zodpovedajúca hodnote 2 je 4, t.j. w₂= 4. Keďže máme v súprave dva predmety s hmotnosťou 3 a 4 a hmotnosť batohu je 7. Do batohu môžeme vložiť predmet s hmotnosťou 4 a 3 a zisky zodpovedajúce hmotnostiam sú 2 a 3; preto je celkový zisk 5, takže pripočítame 5 na M[2][7], ako je uvedené nižšie:

Teraz sa hodnota „i“ zvýši a stane sa 3.

Keď i = 3, W = 1

matematická trieda java

Hmotnosť zodpovedajúca hodnote 3 je 5, t.j. w₃= 5. Keďže v súprave máme tri predmety s hmotnosťou 3, 4 a 5 a hmotnosť batohu je 1. Ani jeden z predmetov nemôžeme dať do batohu, preto pripočítame 0 na M[3][ 1] zobrazené nižšie:

Keď i = 3, W = 2

Hmotnosť zodpovedajúca hodnote 3 je 5, t.j. w₃= 5. Keďže v súprave máme tri predmety s hmotnosťou 3, 4 a 5 a hmotnosť batohu je 1. Ani jeden z predmetov nemôžeme dať do batohu, preto pripočítame 0 na M[3][ 2] zobrazené nižšie:

Keď i = 3, W = 3

Hmotnosť zodpovedajúca hodnote 3 je 5, t.j. w₃= 5. Keďže v sade máme tri položky hmotnosti 3, 4 a 5 a hmotnosť batohu je 3. Predmet s hmotnosťou 3 je možné vložiť do batohu a zisk zodpovedajúci položke je 2, takže pridáme 2 na M[3][3], ako je uvedené nižšie:

Keď i = 3, W = 4

Hmotnosť zodpovedajúca hodnote 3 je 5, t.j. w₃= 5. Keďže v sade máme tri položky s hmotnosťou 3, 4 a 5 a hmotnosť batohu je 4. Môžeme si ponechať položku s hmotnosťou 3 alebo 4; zisk (3) zodpovedajúci váhe 4 je väčší ako zisk zodpovedajúci váhe 3, takže pripočítame 3 na M[3][4], ako je uvedené nižšie:

Keď i = 3, W = 5

Hmotnosť zodpovedajúca hodnote 3 je 5, t.j. w₃= 5. Keďže v sade máme tri položky s hmotnosťou 3, 4 a 5 a hmotnosť batohu je 5. Môžeme si ponechať položku s hmotnosťou 3, 4 alebo 5; zisk (3) zodpovedajúci váhe 4 je väčší ako zisk zodpovedajúci váhe 3 a 5, takže pripočítame 3 na M[3][5], ako je uvedené nižšie:

Keď i = 3, W = 6

Hmotnosť zodpovedajúca hodnote 3 je 5, t.j. w₃= 5. Keďže v sade máme tri položky s hmotnosťou 3, 4 a 5 a hmotnosť batohu je 6. Môžeme si ponechať položku s hmotnosťou 3, 4 alebo 5; zisk (3) zodpovedajúci váhe 4 je väčší ako zisk zodpovedajúci váhe 3 a 5, takže pripočítame 3 na M[3][6], ako je uvedené nižšie:

Keď i = 3, W = 7

Hmotnosť zodpovedajúca hodnote 3 je 5, t.j. w₃= 5. Keďže v sade máme tri položky hmotnosti 3, 4 a 5 a hmotnosť batohu je 7. V tomto prípade si môžeme ponechať obe položky hmotnosti 3 a 4, súčet zisku by sa rovnalo (2 + 3), t.j. 5, takže pridáme 5 na M[3][7], ako je uvedené nižšie:

Keď i = 3, W = 8

Hmotnosť zodpovedajúca hodnote 3 je 5, t.j. w₃= 5. Keďže v sade máme tri položky s hmotnosťou 3, 4 a 5 a hmotnosť batohu je 8. V tomto prípade môžeme ponechať obe položky s hmotnosťou 3 a 4, súčet zisk by sa rovnal (2 + 3), t.j. 5, takže pripočítame 5 na M[3][8], ako je uvedené nižšie:

Teraz sa hodnota „i“ zvýši a stane sa 4.

Keď i = 4, W = 1

Hmotnosť zodpovedajúca hodnote 4 je 6, t.j. w₄= 6. Keďže máme štyri položky v sade váh 3, 4, 5 a 6 a hmotnosť batohu je 1. Hmotnosť všetkých položiek je väčšia ako hmotnosť batohu, takže nemôžeme pridajte akúkoľvek položku do batohu; Preto pridáme 0 na M[4][1], ako je uvedené nižšie:

Keď i = 4, W = 2

Hmotnosť zodpovedajúca hodnote 4 je 6, t.j. w₄= 6. Keďže máme štyri položky v sade váh 3, 4, 5 a 6 a hmotnosť batohu je 2. Hmotnosť všetkých položiek je väčšia ako hmotnosť batohu, takže nemôžeme pridajte akúkoľvek položku do batohu; Preto pridáme 0 na M[4][2], ako je uvedené nižšie:

Keď i = 4, W = 3

Hmotnosť zodpovedajúca hodnote 4 je 6, t.j. w₄= 6. Keďže máme štyri položky v sade váh 3, 4, 5 a 6 a hmotnosť batohu je 3. Predmet s váhou 3 je možné vložiť do batohu a zisk zodpovedajúci hmotnosť 4 je 2, takže pridáme 2 na M[4][3], ako je uvedené nižšie:

Keď i = 4, W = 4

int do reťazca java

Hmotnosť zodpovedajúca hodnote 4 je 6, t.j. w₄= 6. Keďže v sade váh 3, 4, 5 a 6 máme štyri položky a hmotnosť batohu je 4. Predmet s váhou 4 je možné vložiť do batohu a zisk zodpovedajúci hmotnosť 4 je 3, takže pridáme 3 na M[4][4], ako je uvedené nižšie:

Keď i = 4, W = 5

Hmotnosť zodpovedajúca hodnote 4 je 6, t.j. w₄= 6. Keďže v sade váh 3, 4, 5 a 6 máme štyri položky a hmotnosť batohu je 5. Predmet s váhou 4 je možné vložiť do batohu a zisk zodpovedajúci váha 4 je 3, takže pridáme 3 na M[4][5], ako je uvedené nižšie:

Keď i = 4, W = 6

Hmotnosť zodpovedajúca hodnote 4 je 6, t.j. w₄= 6. Keďže máme štyri položky v sade s váhami 3, 4, 5 a 6 a hmotnosť batohu je 6. V tomto prípade môžeme položky do batohu vložiť buď s váhou 3, 4 , 5 alebo 6, ale zisk, t. j. 4 zodpovedajúci váhe 6, je najvyšší spomedzi všetkých položiek; preto pridáme 4 na M[4][6], ako je uvedené nižšie:

Keď i = 4, W = 7

Hmotnosť zodpovedajúca hodnote 4 je 6, t.j. w₄= 6. Keďže v sade závaží 3, 4, 5 a 6 máme štyri položky a hmotnosť batohu je 7. Ak v tomto prípade spočítame dve položky s hmotnosťou 3 a 4, vyprodukuje sa max. zisk, t.j. (2 + 3) sa rovná 5, takže pridáme 5 na M[4][7], ako je uvedené nižšie:

Keď i = 4, W = 8

Hmotnosť zodpovedajúca hodnote 4 je 6, t.j. w₄= 6. Keďže v sade závaží 3, 4, 5 a 6 máme štyri položky a hmotnosť batohu je 8. Ak v tomto prípade spočítame dve položky s hmotnosťou 3 a 4, získame maximum zisk, t.j. (2 + 3) sa rovná 5, takže pripočítame 5 na M[4][8], ako je uvedené nižšie:

Ako môžeme vidieť v tabuľke vyššie, 5 je maximálny zisk spomedzi všetkých položiek. Ukazovateľ ukazuje na posledný riadok a posledný stĺpec s hodnotou 5. Teraz porovnáme hodnotu 5 s predchádzajúcim riadkom; ak predchádzajúci riadok, t.j. i = 3 obsahuje rovnakú hodnotu 5, potom sa ukazovateľ posunie nahor. Keďže predchádzajúci riadok obsahuje hodnotu 5, ukazovateľ sa posunie nahor, ako je uvedené v tabuľke nižšie:

Opäť porovnáme hodnotu 5 z vyššie uvedeného riadku, t.j. i = 2. Keďže vyššie uvedený riadok obsahuje hodnotu 5, ukazovateľ sa opäť posunie nahor, ako je uvedené v tabuľke nižšie:

Opäť porovnáme hodnotu 5 z vyššie uvedeného riadku, t.j. i = 1. Keďže vyššie uvedený riadok neobsahuje rovnakú hodnotu, budeme uvažovať riadok i=1 a váha zodpovedajúca riadku je 4. Preto , vybrali sme váhu 4 a zamietli sme váhy 5 a 6 zobrazené nižšie:

x = { 1, 0, 0}

Zisk zodpovedajúci váhe je 3. Preto sa zostávajúci zisk (5 - 3) rovná 2. Teraz túto hodnotu 2 porovnáme s riadkom i = 2. Keďže riadok (i = 1) obsahuje hodnotu 2 ; preto sa ukazovateľ posunul nahor, ako je znázornené nižšie:

Opäť porovnáme hodnotu 2 s vyššie uvedeným riadkom, t.j. i = 1. Keďže riadok i = 0 neobsahuje hodnotu 2, vyberie sa riadok i = 1 a zobrazí sa váha zodpovedajúca i = 1 nižšie:

X = {1, 1, 0, 0}

Zisk zodpovedajúci váhe je 2. Preto je zostávajúci zisk 0. Hodnotu 0 porovnáme s vyššie uvedeným riadkom. Keďže vyššie uvedený riadok obsahuje hodnotu 0, ale zisk zodpovedajúci tomuto riadku je 0. V tomto probléme sú vybrané dve váhy, t. j. 3 a 4, aby sa zisk maximalizoval.