V tomto tutoriálu, dříve jsme diskutovali Frakční problém Batohu pomocí Greedy přístup. Ukázali jsme, že chamtivý přístup poskytuje optimální řešení pro frakční batoh. Tato kapitola se však bude týkat problému 0-1 batohu a jeho analýzy.
v batohu 0-1 nelze položky rozbít, což znamená, že zloděj by měl vzít položku jako celek nebo by ji měl opustit., To je důvod, proč to nazýváme jako batoh 0-1.
proto v případě 0-1 batohu může být hodnota xi buď 0 nebo 1, kde ostatní omezení zůstávají stejná.
0-1 batoh nelze vyřešit chamtivým přístupem. Chamtivý přístup nezajišťuje optimální řešení. V mnoha případech může chamtivý přístup poskytnout optimální řešení.
následující příklady stanoví naše prohlášení.
Příklad 1
uvažujme, že kapacita batohu je W = 25 a položky jsou uvedeny v následující tabulce.,
| Item | a | b | >
c |
d |
|---|---|---|---|---|
| profit | 24 | 18 | 18 | 10 |
| 24 | 10 | 10 | 7 |
bez ohledu na zisk na jednotku hmotnosti (pi / Wi), pokud použijeme chamtivý přístup k vyřešení tohoto problému, bude vybrána první položka a, protože přispěje k maximálnímu zisku mezi všemi prvky.,
po výběru položky a nebude vybrána žádná další položka. Z tohoto důvodu je pro tento soubor položek celkový zisk 24. Zatímco optimální řešení lze dosáhnout výběrem položek, B A C, kde celkový zisk je 18 + 18 = 36.
příklad-2
Namísto výběru položek na základě celkového přínosu jsou v tomto příkladu položky vybrány na základě poměru pi / wi. Uvažujme, že kapacita batohu je W = 60 a položky jsou uvedeny v následující tabulce.,
| Item | A | B | C |
|---|---|---|---|
| Price | 100 | 280 | 120 |
| Weight | 10 | 40 | 20 |
| Ratio | 10 | 7 | 6 |
Using the Greedy approach, first item A is selected. Then, the next item B is chosen. Hence, the total profit is 100 + 280 = 380., Optimálního řešení této instance však lze dosáhnout výběrem položek B A C, kde celkový zisk je 280 + 120 = 400.
lze tedy dospět k závěru, že chamtivý přístup nemusí poskytnout optimální řešení.
pro řešení 0-1 batohu je vyžadován dynamický programovací přístup.
Prohlášení o problému
zloděj okrádá obchod a může nést maximální hmotnost W do batohu. Existují n položky a hmotnost ith položky je wi a zisk z výběru této položky je pi. Jaké předměty by měl zloděj vzít?,
Dynamic-Programming Approach
dovolte mi být nejvyšší číslovanou položkou v optimálním řešení S Pro W dolary. Pak je s ‚ = s – {i} optimálním řešením pro W-Wi dolary a hodnota řešení s je Vi plus hodnota dílčího problému.
tuto skutečnost můžeme vyjádřit v následujícím vzorci: definujte c jako řešení pro položky 1,2,…, i a maximální hmotnost w.,
algoritmus má následující vstupy
-
maximální hmotnost W
-
počet položek n
-
dvě sekvence v = <V1, v2, …, vn> a w = <W1, W2, …, WN>
soubor položek, které je třeba vzít, lze odvodit z tabulky, počínaje C a sledováním zpět, odkud pocházejí optimální hodnoty.
analýza
tento algoritmus trvá θ(n, w) časy jako tabulka C má (n + 1).(w + 1) položky, kde každá položka vyžaduje θ (1) čas pro výpočet.,