Zde je batoh jako nádoba nebo taška. Předpokládejme, že jsme dali nějaké položky, které mají nějakou váhu nebo zisk. Některé položky musíme dát do batohu tak, aby celková hodnota vyprodukovala maximální zisk.

Například hmotnost nádoby je 20 kg. Položky musíme vybírat tak, aby součet hmotnosti položek byl buď menší nebo roven hmotnosti kontejneru a zisk měl být maximální.

Existují dva typy problémů s batohem:

• 0/1 problém s batohem
• Problém s částečným batohem

Oba problémy probereme jeden po druhém. Nejprve se dozvíme o problému batohu 0/1.

Jaký je problém batohu 0/1?

Problém s batohem 0/1 znamená, že položky jsou buď úplně, nebo nejsou v batohu žádné položky. Například máme dvě položky o hmotnosti 2 kg a 3 kg. Pokud vybereme 2kg položku, pak nemůžeme vybrat 1kg položku z 2kg položky (položka není dělitelná); 2kg položku musíme vybrat úplně. Toto je problém batohu 0/1, ve kterém buď vybereme položku úplně, nebo vybereme tuto položku. Problém batohu 0/1 je řešen dynamickým programováním.

Jaký je problém frakčního batohu?

Problém frakčního batohu znamená, že můžeme položku rozdělit. Například máme položku 3 kg, pak můžeme vybrat položku 2 kg a nechat položku 1 kg. Problém frakčního batohu je vyřešen přístupem Greedy.

Příklad problému s batohem 0/1.

Zvažte problém s váhami a zisky:

Hmotnosti: {3, 4, 6, 5}

Zisky: {2, 3, 1, 4}

Hmotnost batohu je 8 kg

Počet položek je 4

Výše uvedený problém lze vyřešit pomocí následující metody:

X_i= {1, 0, 0, 1}

= {0, 0, 0, 1}

java jak převést řetězec na int

= {0, 1, 0, 1}

Výše uvedené jsou možné kombinace. 1 znamená, že položka je zcela vybrána a 0 znamená, že není vybrána žádná položka. Vzhledem k tomu, že existují 4 položky, možné kombinace budou:

2⁴= 16; Tak. Existuje 16 možných kombinací, které lze vytvořit pomocí výše uvedeného problému. Jakmile jsou vytvořeny všechny kombinace, musíme vybrat kombinaci, která poskytuje maximální zisk.

Dalším přístupem k řešení problému je přístup dynamického programování. V přístupu dynamického programování se složitý problém rozdělí na dílčí problémy, pak najdeme řešení dílčího problému a řešení dílčího problému se použije k nalezení řešení složitého problému.

Jak lze tento problém vyřešit pomocí přístupu dynamického programování?

První,

vytvoříme matici zobrazenou níže:

Ve výše uvedené matici představují sloupce váhu, tj. 8. Řádky představují zisky a váhy položek. Zde jsme nebrali přímo váhu 8, problém je rozdělen na dílčí problémy, tj. 0, 1, 2, 3, 4, 5, 6, 7, 8. Řešení dílčích problémů by bylo uloženo v buňky a odpověď na problém by byla uložena v konečné buňce. Nejprve zapíšeme váhy ve vzestupném pořadí a zisky podle jejich vah uvedených níže:

v_i= {3, 4, 5, 6}

p_i= {2, 3, 4, 1}

První řádek a první sloupec by byly 0, protože pro w=0 neexistuje žádná položka

Když i=1, W=1

v₁= 3; Vzhledem k tomu, že v sadě máme pouze jednu položku o hmotnosti 3, ale kapacita batohu je 1. Nemůžeme naplnit položku 3 kg v batohu o kapacitě 1 kg, takže přidejte 0 na M[1][1] zobrazené níže :

Když i = 1, W = 2

v₁= 3; Vzhledem k tomu, že v sadě máme pouze jednu položku o hmotnosti 3, ale kapacita batohu je 2. Nemůžeme naplnit položku 3 kg v batohu o kapacitě 2 kg, takže přidejte 0 na M[1][2] zobrazené níže :

Když i=1, W=3

v₁= 3; Vzhledem k tomu, že v sadě máme pouze jeden předmět s hmotností rovnou 3 a hmotnost batohu je také 3; proto můžeme batoh naplnit položkou o váze rovné 3. Zisk odpovídající váze 3, tj. 2, vložíme na M[1][3], jak je znázorněno níže:

Když i=1, W=4

_W1= 3; Protože v sadě máme pouze jeden předmět s hmotností rovnou 3 a hmotnost batohu je 4; proto můžeme batoh naplnit položkou o váze rovné 3. Zisk odpovídající váze 3, tj. 2, vložíme na M[1][4], jak je znázorněno níže:

Když i=1, W=5

_W1= 3; Protože máme v sadě pouze jeden předmět s hmotností rovnou 3 a hmotnost batohu je 5; proto můžeme batoh naplnit položkou o váze rovné 3. Zisk odpovídající váze 3, tj. 2, vložíme na M[1][5], jak je znázorněno níže:

Když i = 1, W = 6

_W1= 3; Protože v sadě máme pouze jeden předmět o hmotnosti 3 a váha batohu 6; proto můžeme batoh naplnit položkou o hmotnosti rovné 3. Zisk odpovídající váze 3, tj. 2, vložíme na M[1][6], jak je znázorněno níže:

Když i=1, W=7

_W1= 3; Vzhledem k tomu, že v sadě máme pouze jeden předmět s hmotností rovnou 3 a hmotnost batohu je 7; proto můžeme batoh naplnit položkou o váze rovné 3. Zisk odpovídající váze 3, tj. 2, vložíme na M[1][7], jak je znázorněno níže:

Když i = 1, W = 8

_W1= 3; Protože máme v sadě pouze jeden předmět o hmotnosti 3 a váha batohu je 8; proto můžeme batoh naplnit položkou o váze rovné 3. Zisk odpovídající váze 3, tj. 2, vložíme na M[1][8], jak je znázorněno níže:

Nyní se hodnota 'i' zvýší a stane se 2.

Když i = 2, W = 1

Hmotnost odpovídající hodnotě 2 je 4, tj. w₂= 4. Protože máme v sadě pouze jeden předmět s hmotností rovnou 4 a váha batohu je 1. Nemůžeme dát předmět o hmotnosti 4 do batohu, tak přidáme 0 na M[2][1 ] zobrazeno níže:

Když i = 2, W = 2

Hmotnost odpovídající hodnotě 2 je 4, tj. w₂= 4. Protože máme v sadě pouze jeden předmět o hmotnosti 4 a váha batohu je 2. Nemůžeme dát předmět o hmotnosti 4 do batohu, tak přidáme 0 na M[2][2 ] zobrazeno níže:

Když i = 2, W = 3

Hmotnost odpovídající hodnotě 2 je 4, tj. w₂= 4. Protože máme v sadě dva předměty o hmotnosti 3 a 4 a váha batohu je 3. Můžeme dát předmět o hmotnosti 3 do batohu, tak přidáme 2 na M[2][3] zobrazeno níže:

Když i = 2, W = 4

Hmotnost odpovídající hodnotě 2 je 4, tj. w₂= 4. Protože máme v sadě dva předměty o váze 3 a 4 a váha batohu je 4. Do batohu můžeme vložit předmět o váze 4, protože zisk odpovídající váze 4 je větší než předmět o váze 3, takže přidáme 3 na M[2][4], jak je uvedeno níže:

Když i = 2, W = 5

Hmotnost odpovídající hodnotě 2 je 4, tj. w₂= 4. Protože máme v sadě dva předměty o hmotnosti 3 a 4 a váha batohu je 5. Do batohu můžeme dát předmět o hmotnosti 4 a zisk odpovídající hmotnosti je 3, tak přičteme 3 při M[2][5] zobrazeno níže:

Když i = 2, W = 6

Hmotnost odpovídající hodnotě 2 je 4, tj. w₂= 4. Protože máme v sadě dva předměty o váze 3 a 4 a váha batohu je 6. Do batohu můžeme dát předmět o váze 4 a zisk odpovídající hmotnosti je 3, tak přičteme 3 při M[2][6] zobrazeno níže:

Když i = 2, W = 7

Hmotnost odpovídající hodnotě 2 je 4, tj. w₂= 4. Protože máme v sadě dva předměty o váze 3 a 4 a váha batohu je 7. Můžeme dát předmět o váze 4 a 3 do batohu a zisky odpovídající vahám jsou 2 a 3; proto je celkový zisk 5, takže přidáme 5 na M[2][7], jak je uvedeno níže:

Když i = 2, W = 8

Hmotnost odpovídající hodnotě 2 je 4, tj. w₂= 4. Protože máme v sadě dva předměty o váze 3 a 4 a váha batohu je 7. Můžeme dát předmět o váze 4 a 3 do batohu a zisky odpovídající vahám jsou 2 a 3; proto je celkový zisk 5, takže přidáme 5 na M[2][7], jak je uvedeno níže:

Nyní se hodnota 'i' zvýší a stane se 3.

Když i = 3, W = 1

vypsat řetězec java

Hmotnost odpovídající hodnotě 3 je 5, tj. w₃= 5. Protože v sadě máme tři předměty o hmotnosti 3, 4 a 5 a váha batohu je 1. Nemůžeme do batohu vložit ani jeden z předmětů, tak přidáme 0 na M[3][ 1] zobrazeno níže:

Když i = 3, W = 2

Hmotnost odpovídající hodnotě 3 je 5, tj. w₃= 5. Protože máme v sadě tři předměty o hmotnosti 3, 4 a 5 a váha batohu je 1. Nemůžeme do batohu vložit ani jeden z předmětů, tak přidáme 0 na M[3][ 2] zobrazeno níže:

Když i = 3, W = 3

Hmotnost odpovídající hodnotě 3 je 5, tj. w₃= 5. Protože v sadě máme tři položky o váze 3, 4 a 5 a váha batohu je 3. Do batohu lze vložit položku o váze 3 a zisk odpovídající položce je 2, takže přidáme 2 na M[3][3], jak je uvedeno níže:

Když i = 3, W = 4

Hmotnost odpovídající hodnotě 3 je 5, tj. w₃= 5. Protože máme v sadě tři předměty o hmotnosti 3, 4 a 5 a váha batohu je 4. Můžeme si ponechat předmět o hmotnosti 3 nebo 4; zisk (3) odpovídající váze 4 je větší než zisk odpovídající váze 3, takže přidáme 3 na M[3][4], jak je uvedeno níže:

Když i = 3, W = 5

Hmotnost odpovídající hodnotě 3 je 5, tj. w₃= 5. Protože máme v sadě tři položky o hmotnosti 3, 4 a 5 a hmotnost batohu je 5. Můžeme si ponechat položku o hmotnosti 3, 4 nebo 5; zisk (3) odpovídající váze 4 je větší než zisk odpovídající váze 3 a 5, takže přidáme 3 na M[3][5], jak je uvedeno níže:

Když i = 3, W = 6

Hmotnost odpovídající hodnotě 3 je 5, tj. w₃= 5. Protože v sadě máme tři předměty o hmotnosti 3, 4 a 5 a váha batohu je 6. Můžeme si ponechat předmět o hmotnosti 3, 4 nebo 5; zisk (3) odpovídající váze 4 je větší než zisk odpovídající váze 3 a 5, takže přidáme 3 na M[3][6], jak je znázorněno níže:

Když i = 3, W = 7

Hmotnost odpovídající hodnotě 3 je 5, tj. w₃= 5. Protože v sadě máme tři položky o hmotnosti 3, 4 a 5 a váha batohu je 7. V tomto případě si můžeme ponechat obě položky hmotnosti 3 a 4, součet zisku by se rovnalo (2 + 3), tj. 5, takže přidáme 5 na M[3][7], jak je uvedeno níže:

Když i = 3, W = 8

Hmotnost odpovídající hodnotě 3 je 5, tj. w₃= 5. Protože máme tři položky v sadě hmotnosti 3, 4 a 5 a hmotnost batohu je 8. V tomto případě můžeme ponechat obě položky hmotnosti 3 a 4, součet hmotnosti zisk by se rovnal (2 + 3), tj. 5, takže přidáme 5 na M[3][8], jak je uvedeno níže:

Nyní se hodnota 'i' zvýší a stane se 4.

řetězec do int java

Když i = 4, W = 1

Hmotnost odpovídající hodnotě 4 je 6, tj. w₄= 6. Protože máme čtyři položky v sadě závaží 3, 4, 5 a 6 a hmotnost batohu je 1. Hmotnost všech položek je větší než hmotnost batohu, takže nemůžeme přidat jakoukoli položku do batohu; Proto přidáme 0 na M[4][1], jak je uvedeno níže:

Když i = 4, W = 2

Hmotnost odpovídající hodnotě 4 je 6, tj. w₄= 6. Protože máme čtyři položky v sadě závaží 3, 4, 5 a 6 a hmotnost batohu je 2. Hmotnost všech položek je větší než hmotnost batohu, takže nemůžeme přidat jakoukoli položku do batohu; Proto přidáme 0 na M[4][2], jak je uvedeno níže:

Když i = 4, W = 3

Hmotnost odpovídající hodnotě 4 je 6, tj. w₄= 6. Protože v sadě o váze 3, 4, 5 a 6 máme čtyři položky a váha batohu je 3. Předmět o váze 3 lze vložit do batohu a zisk odpovídající váha 4 je 2, takže přidáme 2 na M[4][3], jak je uvedeno níže:

Když i = 4, W = 4

Hmotnost odpovídající hodnotě 4 je 6, tj. w₄= 6. Protože v sadě o váze 3, 4, 5 a 6 máme čtyři položky a váha batohu je 4. Předmět o váze 4 lze vložit do batohu a zisk odpovídající váha 4 je 3, takže přidáme 3 na M[4][4], jak je uvedeno níže:

Když i = 4, W = 5

Hmotnost odpovídající hodnotě 4 je 6, tj. w₄= 6. Protože v sadě o váze 3, 4, 5 a 6 máme čtyři položky a váha batohu je 5. Předmět o váze 4 lze vložit do batohu a zisk odpovídající váha 4 je 3, takže přidáme 3 na M[4][5], jak je uvedeno níže:

Když i = 4, W = 6

Hmotnost odpovídající hodnotě 4 je 6, tj. w₄= 6. Vzhledem k tomu, že máme čtyři položky v sadě závaží 3, 4, 5 a 6 a hmotnost batohu je 6. V tomto případě můžeme položky vložit do batohu buď o hmotnosti 3, 4 , 5 nebo 6, ale zisk, tj. 4 odpovídající váze 6, je nejvyšší ze všech položek; proto přidáme 4 na M[4][6], jak je uvedeno níže:

Když i = 4, W = 7

Hmotnost odpovídající hodnotě 4 je 6, tj. w₄= 6. Vzhledem k tomu, že máme čtyři položky v sadě závaží 3, 4, 5 a 6 a hmotnost batohu je 7. Zde, když sečteme dvě položky závaží 3 a 4, vyprodukuje maximum zisk, tj. (2 + 3) se rovná 5, takže přidáme 5 na M[4][7], jak je uvedeno níže:

Když i = 4, W = 8

Hmotnost odpovídající hodnotě 4 je 6, tj. w₄= 6. Vzhledem k tomu, že máme čtyři položky v sadě závaží 3, 4, 5 a 6 a hmotnost batohu je 8. Zde, když sečteme dvě položky závaží 3 a 4, vyprodukuje maximum zisk, tj. (2 + 3) se rovná 5, takže přidáme 5 na M[4][8], jak je uvedeno níže:

Jak můžeme vidět ve výše uvedené tabulce, 5 je maximální zisk ze všech položek. Ukazatel ukazuje na poslední řádek a poslední sloupec s hodnotou 5. Nyní porovnáme hodnotu 5 s předchozím řádkem; pokud předchozí řádek, tj. i = 3 obsahuje stejnou hodnotu 5, posune se ukazatel nahoru. Protože předchozí řádek obsahuje hodnotu 5, ukazatel se posune nahoru, jak je uvedeno v tabulce níže:

Opět porovnáme hodnotu 5 z výše uvedeného řádku, tj. i = 2. Protože výše uvedený řádek obsahuje hodnotu 5, bude ukazatel opět posunut nahoru, jak je uvedeno v tabulce níže:

Opět porovnáme hodnotu 5 z výše uvedeného řádku, tj. i = 1. Protože výše uvedený řádek neobsahuje stejnou hodnotu, budeme uvažovat řádek i=1 a váha odpovídající řádku je 4. Proto , vybrali jsme váhu 4 a odmítli jsme váhy 5 a 6 zobrazené níže:

x = { 1, 0, 0}

Zisk odpovídající váze je 3. Zbývající zisk je tedy (5 - 3) roven 2. Nyní tuto hodnotu 2 porovnáme s řádkem i = 2. Protože řádek (i = 1) obsahuje hodnotu 2 ; proto se ukazatel posunul nahoru, jak je znázorněno níže:

Opět porovnáme hodnotu 2 s výše uvedeným řádkem, tj. i = 1. Protože řádek i =0 neobsahuje hodnotu 2, vybere se řádek i = 1 a zobrazí se váha odpovídající i = 1 níže:

X = {1, 1, 0, 0}

Zisk odpovídající váze je 2. Zbývající zisk je tedy 0. Hodnotu 0 porovnáme s výše uvedeným řádkem. Protože výše uvedený řádek obsahuje hodnotu 0, ale zisk odpovídající tomuto řádku je 0. V tomto problému jsou vybrány dvě váhy, tj. 3 a 4 pro maximalizaci zisku.