Itt a hátizsák olyan, mint egy konténer vagy egy táska. Tegyük fel, hogy megadtunk néhány tételt, amelyeknek súlya vagy nyeresége van. Néhány tárgyat úgy kell a hátizsákba helyeznünk, hogy az összérték maximális profitot termeljen.

Például a tartály súlya 20 kg. A tételeket úgy kell kiválasztanunk, hogy a tételek súlyának összege kisebb vagy egyenlő legyen, mint a konténer súlya, és a haszon maximális legyen.

Kétféle hátizsák probléma létezik:

• 0/1 hátizsák probléma
• Töredékes hátizsák probléma

Mindkét problémát egyenként megbeszéljük. Először is megismerjük a 0/1 hátizsák problémát.

Mi a 0/1 hátizsák probléma?

A 0/1-es hátizsák-probléma azt jelenti, hogy a cikkek vagy teljesen meg vannak töltve, vagy egyetlen elem sem került a hátizsákba. Például van két termékünk, amelyek súlya 2 kg, illetve 3 kg. Ha a 2 kg-os terméket választjuk, akkor a 2 kg-osból nem tudunk 1 kg-ot kiválasztani (a tétel nem osztható); teljesen ki kell választanunk a 2 kg-os tételt. Ez egy 0/1-es hátizsák-probléma, amelyben vagy teljesen kiválasztjuk az elemet, vagy mi választjuk ki azt. A 0/1 hátizsák problémát a dinamikus programozás oldja meg.

Mi a frakcionált hátizsák probléma?

A tört hátizsák probléma azt jelenti, hogy fel tudjuk osztani az elemet. Például van egy 3 kg-os cikkünk, akkor kiválaszthatjuk a 2 kg-ost, és elhagyhatjuk az 1 kg-ost. A töredékes hátizsák problémát a Greedy megközelítés oldja meg.

Példa a 0/1-es hátizsák problémájára.

Tekintsük azt a problémát, hogy a súlyok és a nyereség a következő:

Súlyok: {3, 4, 6, 5}

Nyereség: {2, 3, 1, 4}

A hátizsák súlya 8 kg

A tételek száma 4

A fenti probléma a következő módszerrel oldható meg:

x_én= {1, 0, 0, 1}

= {0, 0, 0, 1}

próbáld meg elkapni a java blokkot

= {0, 1, 0, 1}

A fentiek a lehetséges kombinációk. Az 1 azt jelenti, hogy a tétel teljesen ki van szedve, a 0 pedig azt, hogy egyetlen tételt sem vettek fel. Mivel 4 elem van, a lehetséges kombinációk a következők lesznek:

2⁴= 16; Így. A fenti probléma felhasználásával 16 lehetséges kombináció hozható létre. Ha az összes kombináció elkészült, ki kell választanunk a maximális profitot biztosító kombinációt.

A probléma megoldásának másik módja a dinamikus programozási megközelítés. A dinamikus programozási megközelítésben a bonyolult problémát részproblémákra bontjuk, majd egy részprobléma megoldását találjuk meg, és a részprobléma megoldását egy összetett probléma megoldására használjuk.

Hogyan lehet ezt a problémát megoldani a dinamikus programozási megközelítés használatával?

Első,

mátrixot készítünk az alábbiak szerint:

A fenti mátrixban az oszlopok a súlyt, azaz a 8-at jelentik. A sorok a tételek nyereségét és súlyát jelentik. Itt nem vettük közvetlenül a 8-as súlyt, a feladat részproblémákra oszlik, azaz 0, 1, 2, 3, 4, 5, 6, 7, 8. A részfeladatok megoldása a cellák és a probléma megoldása az utolsó cellában kerül tárolásra. Először írjuk fel a súlyokat növekvő sorrendben és a nyereséget súlyuk szerint az alábbiak szerint:

Ban ben_én= {3, 4, 5, 6}

p_én= {2, 3, 4, 1}

Az első sor és az első oszlop 0 lenne, mivel a w=0 esetén nincs elem

Ha i=1, W=1

Ban ben₁= 3; Mivel a készletben csak egy 3-as súlyú cikkünk van, de a hátizsák kapacitása 1. Az 1 kg-os hátizsákba nem tudjuk kitölteni a 3 kg-os elemet, ezért adjunk hozzá 0-t az M[1][1] pontnál az alábbiak szerint. :

Ha i = 1, W = 2

Ban ben₁= 3; Mivel a készletben csak egy 3-as súlyú cikkünk van, de a hátizsák kapacitása 2. A 2 kg-os hátizsákba nem tudjuk kitölteni a 3 kg-os elemet, ezért adjunk hozzá 0-t az M[1][2] pontnál az alábbiak szerint. :

Ha i=1, W=3

Ban ben₁= 3; Mivel a készletben csak egy olyan elemünk van, amelynek súlya egyenlő 3, és a hátizsák súlya is 3; ezért megtölthetjük a hátizsákot egy 3-as súlyú elemmel. A 3-as súlynak megfelelő nyereséget, azaz 2-t teszünk M[1][3]-nál az alábbiak szerint:

Ha i=1, W=4

_W1= 3; Mivel a készletben csak egy olyan elemünk van, amelynek súlya 3, a hátizsák súlya pedig 4; ezért a hátizsákot megtölthetjük egy 3-as súlyú elemmel. A 3-as súlynak megfelelő nyereséget, azaz 2-t teszünk M[1][4]-re, az alábbiak szerint:

Ha i=1, W=5

_W1= 3; Mivel a készletben csak egy olyan elemünk van, amelynek súlya egyenlő 3, és a hátizsák súlya 5; ezért megtölthetjük a hátizsákot egy 3-as súlyú elemmel. A 3-as súlynak megfelelő nyereséget, azaz 2-t teszünk M[1][5]-re, az alábbiak szerint:

Ha i = 1, W = 6

_W1= 3; Mivel a készletben csak egy olyan elemünk van, amelynek súlya egyenlő 3, és a hátizsák súlya 6; ezért megtölthetjük a hátizsákot egy 3-as súlyú elemmel. A 3-as súlynak megfelelő nyereséget, azaz 2-t teszünk M[1][6]-nál az alábbiak szerint:

Ha i=1, W=7

_W1= 3; Mivel a készletben csak egy olyan elemünk van, amelynek súlya egyenlő 3, és a hátizsák súlya 7; ezért megtölthetjük a hátizsákot egy 3-as súlyú elemmel. A 3-as súlynak megfelelő nyereséget, azaz 2-t teszünk M[1][7]-re, az alábbiak szerint:

Ha i = 1, W = 8

_W1= 3; Mivel a készletben csak egy olyan elemünk van, amelynek súlya 3, a hátizsák súlya pedig 8; ezért megtölthetjük a hátizsákot egy 3-as súlyú elemmel. A 3-as súlynak megfelelő profitot, azaz 2-t teszünk M[1][8]-nál az alábbiak szerint:

Most az 'i' értéke növekszik, és 2 lesz.

Ha i = 2, W = 1

A 2-es értéknek megfelelő súly 4, azaz w₂= 4. Mivel a halmazban csak egy 4-es súlyú tárgyunk van, és a hátizsák súlya 1. A 4-es súlyú tárgyat nem tehetjük hátizsákba, ezért M[2][1-nél 0-t adunk ] az alábbiak szerint:

Ha i = 2, W = 2

A 2-es értéknek megfelelő súly 4, azaz w₂= 4. Mivel a halmazban csak egy 4-es súlyú tárgyunk van, a hátizsák súlya pedig 2. A 4-es súlyú tárgyat nem tehetjük hátizsákba, ezért M[2][2-nél 0-t adunk ] az alábbiak szerint:

Ha i = 2, W = 3

A 2-es értéknek megfelelő súly 4, azaz w₂= 4. Mivel a készletben két darab 3-as és 4-es súllyal szerepel, a hátizsák súlya pedig 3. A 3-as súlyú tárgyat tehetjük hátizsákba, így M[2][3]-nál adunk hozzá 2-t. az alábbiak szerint látható:

Ha i = 2, W = 4

A 2-es értéknek megfelelő súly 4, azaz w₂= 4. Mivel a készletben két 3-as és 4-es súlyú cikkünk van, és a hátizsák súlya 4. A 4-es súlyú terméket tehetjük egy hátizsákba, mivel a 4-es súlynak megfelelő haszon nagyobb, mint a súlyú tételé. 3, ezért hozzáadunk 3-at az M[2][4] ponthoz, az alábbiak szerint:

Ha i = 2, W = 5

A 2-es értéknek megfelelő súly 4, azaz w₂= 4. Mivel a készletben két darab 3-as és 4-es súllyal szerepel, a hátizsák súlya pedig 5. Egy hátizsákba tehetünk 4-es súlyú terméket és a súlynak megfelelő haszon 3, ezért adunk hozzá 3-at. M[2][5] az alábbiak szerint:

Ha i = 2, W = 6

A 2-es értéknek megfelelő súly 4, azaz w₂= 4. Mivel a készletben két darab 3-as és 4-es súllyal szerepel, a hátizsák súlya pedig 6. Egy hátizsákba tehetünk 4-es súlyú elemet és a súlynak megfelelő haszon 3, ezért adunk hozzá 3-at. M[2][6] az alábbiak szerint:

Ha i = 2, W = 7

A 2-es értéknek megfelelő súly 4, azaz w₂= 4. Mivel a készletben két darab 3-as és 4-es súlyú, a hátizsák súlya pedig 7. A 4-es és 3-as súlyú tételt egy hátizsákba tehetjük, és a súlyoknak megfelelő haszon 2 és 3; ezért a teljes nyereség 5, ezért hozzáadunk 5-öt M[2][7]-nél az alábbiak szerint:

Ha i = 2, W = 8

A 2-es értéknek megfelelő súly 4, azaz w₂= 4. Mivel a készletben két darab 3-as és 4-es súlyú, a hátizsák súlya pedig 7. A 4-es és 3-as súlyú tételt egy hátizsákba tehetjük, és a súlyoknak megfelelő haszon 2 és 3; ezért a teljes nyereség 5, ezért hozzáadunk 5-öt M[2][7]-nél az alábbiak szerint:

Most az 'i' értéke növekszik, és 3 lesz.

Ha i = 3, W = 1

string metódusok java-ban

A 3-as értéknek megfelelő súly 5, azaz w₃= 5. Mivel három elemünk van a készletben, amelyek súlya 3, 4 és 5, és a hátizsák súlya 1. Egyik elemet sem tehetjük hátizsákba, ezért 0-t adunk hozzá M[3][ 1] az alábbiak szerint:

Ha i = 3, W = 2

A 3-as értéknek megfelelő súly 5, azaz w₃= 5. Mivel a készletben három darab 3, 4 és 5 súlyú, és a hátizsák súlya 1. Egyik elemet sem tehetjük hátizsákba, ezért 0-t adunk M[3][ 2] az alábbiak szerint:

Ha i = 3, W = 3

A 3-as értéknek megfelelő súly 5, azaz w₃= 5. Mivel a 3-as, 4-es és 5-ös súlykészletben három darab van, a hátizsák súlya pedig 3. A 3-as súllyal rendelkező cikk a hátizsákba tehető, és a tárgynak megfelelő haszon 2, így hozzáadunk 2-t az M[3][3] ponthoz az alábbiak szerint:

Ha i = 3, W = 4

A 3-as értéknek megfelelő súly 5, azaz w₃= 5. Mivel a 3-as, 4-es és 5-ös súlykészletben három darab van, a hátizsák súlya pedig 4. A 3-as vagy 4-es súlyú tételt megtarthatjuk; a 4-es súlynak megfelelő nyereség (3) nagyobb, mint a 3-as súlynak megfelelő nyereség, ezért hozzáadunk 3-at M[3][4]-nél az alábbiak szerint:

Ha i = 3, W = 5

A 3-as értéknek megfelelő súly 5, azaz w₃= 5. Mivel a 3-as, 4-es és 5-ös súlykészletben három darab van, a hátizsák súlya pedig 5. A 3-as, 4-es vagy 5-ös súlyú tárgyat megtarthatjuk; a 4-es súlynak megfelelő nyereség (3) nagyobb, mint a 3-as és 5-ös súlynak megfelelő nyereség, ezért hozzáadunk 3-at M[3][5]-nél az alábbiak szerint:

Ha i = 3, W = 6

A 3-as értéknek megfelelő súly 5, azaz w₃= 5. Mivel a 3-as, 4-es és 5-ös súlykészletben három darab van, a hátizsák súlya pedig 6. A 3-as, 4-es vagy 5-ös súlyú darabot megtarthatjuk; a 4-es súlynak megfelelő nyereség (3) nagyobb, mint a 3-as és 5-ös súlynak megfelelő nyereség, ezért hozzáadunk 3-at M[3][6]-nál az alábbiak szerint:

Ha i = 3, W = 7

A 3-as értéknek megfelelő súly 5, azaz w₃= 5. Mivel a 3-as, 4-es és 5-ös súlyhalmazban három tételünk van, a hátizsák súlya pedig 7. Ebben az esetben a 3-as és a 4-es súlyú tételeket is megtarthatjuk, a haszon összege egyenlő lenne (2 + 3), azaz 5, ezért hozzáadunk 5-öt az M[3][7] pontban az alábbiak szerint:

Ha i = 3, W = 8

java sorok

A 3-as értéknek megfelelő súly 5, azaz w₃= 5. Mivel a 3-as, 4-es és 5-ös súlyhalmazban három darab van, a hátizsák súlya pedig 8. Ebben az esetben a 3-as és a 4-es súlyú elemeket is megtarthatjuk, így a a nyereség egyenlő lenne (2 + 3), azaz 5, ezért hozzáadunk 5-öt M[3][8]-nál az alábbiak szerint:

Most az „i” értéke növekszik, és 4 lesz.

Ha i = 4, W = 1

A 4-es értéknek megfelelő súly 6, azaz w₄= 6. Mivel a 3-as, 4-es, 5-ös és 6-os súlykészletben négy darab van, és a hátizsák súlya 1. Az összes tárgy súlya nagyobb, mint a hátizsák súlya, ezért nem tudjuk adjon hozzá bármilyen tárgyat a hátizsákba; Ezért 0-t adunk az M[4][1] ponthoz az alábbiak szerint:

Ha i = 4, W = 2

A 4-es értéknek megfelelő súly 6, azaz w₄= 6. Mivel a 3-as, 4-es, 5-ös és 6-os súlykészletben négy darab van, és a hátizsák súlya 2. Az összes elem súlya nagyobb, mint a hátizsák súlya, ezért nem tudjuk adjon hozzá bármilyen tárgyat a hátizsákba; Ezért 0-t adunk az M[4][2] ponthoz az alábbiak szerint:

Ha i = 4, W = 3

A 4-es értéknek megfelelő súly 6, azaz w₄= 6. Mivel a 3-as, 4-es, 5-ös és 6-os súlykészletben négy darab van, és a hátizsák súlya 3. A 3-as súllyal rendelkező cikk a hátizsákba tehető és a haszon megfelel a a 4-es súly 2, ezért hozzáadunk 2-t M[4][3]-nál, az alábbiak szerint:

Ha i = 4, W = 4

A 4-es értéknek megfelelő súly 6, azaz w₄= 6. Mivel a 3-as, 4-es, 5-ös és 6-os súlykészletben négy darab van, és a hátizsák súlya 4. A 4-es súllyal rendelkező cikk a hátizsákba tehető és a haszon megfelel a a 4-es súly 3, tehát 3-at adunk hozzá az M[4][4] ponthoz, az alábbiak szerint:

Ha i = 4, W = 5

A 4-es értéknek megfelelő súly 6, azaz w₄= 6. Mivel a 3-as, 4-es, 5-ös és 6-os súlykészletben négy darab van, és a hátizsák súlya 5. A 4-es súllyal rendelkező cikk a hátizsákba tehető és a haszon megfelel a a 4-es súly 3, tehát 3-at adunk hozzá az M[4][5]-nél az alábbiak szerint:

Ha i = 4, W = 6

A 4-es értéknek megfelelő súly 6, azaz w₄= 6. Mivel a 3-as, 4-es, 5-ös és 6-os súlykészletben négy darab van, a hátizsák súlya pedig 6. Ebben az esetben a 3-as vagy 4-es súlyú tárgyakat a hátizsákba tehetjük. , 5 vagy 6, de a profit, azaz a 6-os súlynak megfelelő 4 a legmagasabb az összes tétel közül; ezért hozzáadunk 4-et az M[4][6] ponthoz az alábbiak szerint:

Ha i = 4, W = 7

A 4-es értéknek megfelelő súly 6, azaz w₄= 6. Mivel a 3-as, 4-es, 5-ös és 6-os súlykészletben négy darab van, és a hátizsák súlya 7. Itt, ha összeadunk két darab 3-as és 4-es súlyt, akkor a maximumot adja profit, azaz (2 + 3) egyenlő 5-tel, ezért hozzáadunk 5-öt M[4][7]-nél az alábbiak szerint:

Ha i = 4, W = 8

A 4-es értéknek megfelelő súly 6, azaz w₄= 6. Mivel a 3-as, 4-es, 5-ös és 6-os súlykészletben négy darab van, és a hátizsák súlya 8. Itt, ha összeadunk két darab 3-as és 4-es súlyt, akkor a maximumot adja profit, azaz (2 + 3) egyenlő 5-tel, ezért hozzáadunk 5-öt M[4][8]-nál az alábbiak szerint:

Ahogy a fenti táblázatban is láthatjuk, az 5 a maximális nyereség az összes bejegyzés között. A mutató az utolsó sorra és az utolsó 5 értékű oszlopra mutat. Most összehasonlítjuk az 5 értéket az előző sorral; ha az előző sor, azaz az i = 3 ugyanazt az 5 értéket tartalmazza, akkor a mutató felfelé tolódik. Mivel az előző sor az 5-ös értéket tartalmazza, így a mutató felfelé tolódik, ahogy az alábbi táblázatban látható:

Ismét összehasonlítjuk a fenti sor 5-ös értékét, azaz i = 2-t. Mivel a fenti sor tartalmazza az 5-ös értéket, így a mutató ismét felfelé tolódik, ahogy az alábbi táblázatban látható:

Ismét összehasonlítjuk a fenti sor 5-ös értékét, azaz i = 1. Mivel a fenti sor nem tartalmazza ugyanazt az értéket, ezért az i=1 sort fogjuk figyelembe venni, és a sornak megfelelő súly 4. , a 4-es súlyt választottuk, és az alább látható 5-ös és 6-os súlyokat elutasítottuk:

x = { 1, 0, 0}

A súlynak megfelelő nyereség 3. Ezért a maradék haszon (5 - 3) egyenlő 2-vel. Most ezt a 2-es értéket hasonlítjuk össze az i = 2 sorral. Mivel az (i = 1) sor tartalmazza a 2-es értéket. ; ezért a mutató felfelé tolódott el az alábbiak szerint:

Ismét összehasonlítjuk a 2 értéket egy fenti sorral, azaz i = 1. Mivel az i =0 sor nem tartalmazza a 2 értéket, így az i = 1 sor kerül kiválasztásra, és az i = 1-nek megfelelő súly 3 jelenik meg. lent:

X = {1, 1, 0, 0}

A súlynak megfelelő nyereség 2. Ezért a maradék nyereség 0. A 0 értéket összehasonlítjuk a fenti sorral. Mivel a fenti sor 0 értéket tartalmaz, de a sornak megfelelő nyereség 0. Ebben a feladatban két súlyozást választunk, azaz a 3-as és a 4-es a profit maximalizálása érdekében.