Update: Přečtěte si o optimalizaci prostor složitost, dynamické programování, řešení v mém navazující článek zde.,
Problém Batohu je opravdu zajímavý problém kombinatorika — citovat Wikipedii,
„vzhledem k tomu, sadu položek, každá o hmotnosti a hodnoty, určení množství každá položka patří do kolekce tak, že celková hmotnost je méně než nebo se rovná dané hranice a celková hodnota je tak velký, jak je to možné.“
z Wikipedie vidíme, že existuje několik variant problému batohu: 0-1 batoh, ohraničený batoh a neomezený batoh., Dnes se zaměříme na nejběžnější (a nejjednodušší) variantu: problém s batohem 0-1.
O něco zajímavější a relatable formulace 0-1 problém batohu je:
Zvážit zloděj dostane do domu, okrást a nosí batoh. V domácnosti je pevný počet položek-každý s vlastní hmotností a hodnotou — šperky, s menší hmotností a nejvyšší hodnotou vs tabulky, s menší hodnotou, ale hodně těžké. Chcete-li přidat palivo do ohně, zloděj má starý batoh, který má omezenou kapacitu., Je zřejmé, že nemůže rozdělit stůl na polovinu nebo šperky na 3/4ths. Buď to vezme, nebo opustí. Zdroj
bohužel jsem měl potíže pochopit některé části článku Hackerearth, a proto jsem se rozhodl napsat svůj vlastní článek. Tento článek bude z velké části založen na článku Hackerearth a fragmenty kódu jsou napsány v Javě. Budu tacking na další vysvětlení a zpracování, kde mám pocit, že jsou nezbytné.
tento problém vyřešíme dynamickým programováním., Dynamické programování vyžaduje optimální podstrukturu a překrývající se dílčí problémy, z nichž oba jsou přítomny v problému 0-1 batohu, jak uvidíme.
je v pořádku, pokud nerozumíte tomu, co jsou“ optimální podstruktura „a“ překrývající se dílčí problémy “ (to je článek na další den). V podstatě, to znamená zvláštní chuť problémy, které nám umožní znovu použít předchozí řešení menších problémů za účelem výpočtu řešení aktuálního problému. Uvidíš, co tím myslím.,
podrobnosti
Protože to je 0-1 problém batohu, buď můžeme zařadit položku v našem batohu, nebo vyloučit to, ale neobsahuje část, nebo zahrnout více krát.
řešení
nejprve vytvoříme 2-dimenzionální pole (tj. tabulku) n + 1 řádky a w + 1 sloupce.
číslo řádku i představuje soubor všech položek z řádků 1— i. Například hodnoty v řádku 3 předpokládá, že máme pouze položky 1, 2 a 3.
číslo sloupce j představuje hmotnostní kapacitu našeho batohu., Hodnoty ve sloupci 5 proto například předpokládají, že náš batoh může obsahovat 5 hmotnostních jednotek.
uvedení všeho dohromady, položka v řádku i, sloupec j představuje maximální hodnotu, kterou lze získat s položkami 1, 2, 3 … i, v batohu, který pojme jednotky hmotnosti j.
zavoláme naši tabulku mat pro matrix. Proto int mat = new int.
Krok 2:
můžeme okamžitě začít vyplňovat některé položky v naší tabulce: základní případy, pro které je řešení triviální., Například v řádku 0, když nemáme žádné položky, z nichž bychom si mohli vybrat, musí být maximální hodnota, která může být uložena v libovolném batohu, 0. Podobně ve sloupci 0 je pro batoh, který pojme 0 hmotnostních jednotek, maximální hodnota, kterou lze v něm uložit, 0. (Předpokládáme, že neexistují žádné hmotnostní, cenné předměty.)
můžeme to udělat 2 smyčky:
3. Krok (jádro problému):
Nyní, chceme začít vyplnění našeho stolu., Stejně jako u všech dynamických programovacích řešení využijeme v každém kroku naše řešení předchozích dílčích problémů.
nejprve popíšu logiku, než ukážu konkrétní příklad.
vztah mezi hodnotou na řádek i, sloupec j a hodnoty na předchozí dílčí problémy je následující:
Připomeňme si, že v řádku i a sloupci j, řešíme dílčí problém, skládající se z položek 1, 2, 3 … jsem s batohem j kapacity. V tomto bodě existují 2 možnosti: můžeme buď zahrnout položku i nebo ne., Proto musíme porovnat maximální hodnotu, kterou můžeme získat s a bez položku já.
maximální hodnota, kterou můžeme získat bez položku, můžete nalézt na řádku i-1, sloupec j. Tato část je snadné. Zdůvodnění je jednoduché: cokoliv maximální hodnotu můžeme získat s body 1, 2, 3 … já, musí být samozřejmě stejné maximální hodnoty můžeme získat s body 1, 2, 3 …, i – 1, pokud se rozhodneme není zahrnout položku já.
vypočítat maximální hodnotu, kterou můžeme získat s bodem jsem, musíme nejprve porovnat hmotnost položky jsem s batohu je nosnost., Je zřejmé, že pokud položka i váží více než to, co může batoh držet, nemůžeme ji zahrnout, takže nemá smysl provádět výpočet. V takovém případě je řešením tohoto problému pouze maximální hodnota, kterou můžeme získat bez položky i (tj. hodnota v řádku výše, ve stejném sloupci).
předpokládejme však, že položka i váží méně než kapacita batohu. Máme tedy možnost ji zahrnout, pokud potenciálně zvyšuje maximální dosažitelnou hodnotu., Maximální dosažitelná hodnota zahrnutím položky i je tedy = hodnota položky i samotné + maximální hodnota, kterou lze získat se zbývající kapacitou batohu. Samozřejmě chceme plně využít kapacity našeho batohu a nenechat žádnou zbývající kapacitu plýtvat.
Proto, že v řádku i a sloupci j (což představuje maximální hodnotu, kterou lze získat zde), budeme vybírat buď maximální hodnota, kterou můžeme získat bez položku jsem se, nebo maximální hodnotu, kterou můžeme získat s bodem jsem podle toho, která hodnota je větší.
zde je konkrétní příklad toho, co mám na mysli.,
Na řádek 3 (bod 2), a sloupci 5 (kapacita 4), můžeme si vybrat buď zahrnout položku 2 (který váží 4 jednotky), nebo ne. Pokud se rozhodneme ji nezahrnout, maximální hodnota, kterou můžeme získat, je stejná, jako kdybychom měli na výběr pouze položku 1 (která se nachází v řádku výše, tj., Chceme-li zahrnout položku 2, maximální hodnotu můžeme získat s bodem 2 je hodnota položky 2 (40) + maximální hodnotu můžeme získat zbývající kapacity (což je 0, protože batoh je zcela plné už).
v řádku 3 (položka 2) a sloupci 10 (kapacita batohu 9) se opět můžeme rozhodnout zahrnout položku 2 nebo ne. Pokud se rozhodneme ne, maximální hodnota, kterou můžeme získat, je stejná jako hodnota v řádku výše ve stejném sloupci, tj. 10 (zahrnutím pouze položky 1, která má hodnotu 10). Pokud zahrneme položku 2, máme zbývající kapacitu batohu 9 – 4 = 5., Maximální hodnotu, kterou lze získat s kapacitou 5, můžeme zjistit pohledem na řádek výše, ve sloupci 5. Maximální hodnota, kterou můžeme získat zahrnutím položky 2, je tedy 40 (hodnota položky 2) + 10 = 50.
vybereme větší z 50 vs 10, a tak maximální hodnota, kterou můžeme získat u položek 1 a 2, s kapacitou batohu 9, je 50.,
tento algoritmus může být vyjádřen v jazyce Java, jako je tento:
Krok 4 (konečné řešení):
Jakmile je tabulka byla naplněna, konečné řešení může být nalezeno na posledním řádku v posledním sloupci, což představuje maximální hodnotu, které lze získat všechny položky a plnou kapacitu batohu.
return mat;
Pracovní kód:
Poznámka:: tady, vytiskla jsem konečnou odpověď, místo návratu, protože vše je umístěno pod public static void main.,
Thanks for reading!