Frakční batoh v lineárním čase

Bylo by hezké, kdybyste uvedli problém. Předpokládám, že máte $ n $ položky $ x_i $ , z nichž každá má zisk $ p_i $ a váha $ w_i $ . Chcete maximalizovat svůj zisk pod omezením, že celková váha je maximálně $ W $ . U každé položky $ x_i $ je povoleno vložit libovolný zlomek $ \ theta \ in [0,1] $ , což vám přinese zisk $ \ theta p_i $ a váhu $ \ theta w_i $ .

Zde je příklad. Máte surové zlato se ziskem 1 000 $ a váhou $ 1 $ . Máte také banány se ziskem $ 1 $ a váhou $ 10 $ . Předpokládejme, že unesete váhu $ 2 $ . Co bys dělal? Přirozeně byste nejdříve vložili tolik zlata, kolik můžete – jmenovitě všechno, a pak byste dali tolik banánů, kolik jen můžete – jmenovitě desetinu z toho pro celkový zisk 1 000,1 $ $ .

Obecný algoritmus je podobný. Předpokládejme, že rozdělíte $ W $ na $ 1000 $ „sloty“, které chcete naplnit co nejvíce ziskové části zboží o hmotnosti $ W / 1000 $ . U položky o hmotnosti $ w_i $ máme $ w_i / (W / 1000) $ kusů (předpokládejme v tuto chvíli celé číslo) a každé z nich má hodnotu $ p_i / (w_i / (W / 1000)) $ . Při výběru toho, co vložit do slotu, bychom chtěli maximalizovat náš zisk, a proto vybereme položku s maximálním $ p_i / w_i $ a vložíme jej tolik kusy, jak je to možné. Pokud dojdeme, vybereme položku s dalším největším $ p_i / w_i $ atd.

Můžete to implementovat bez dělení $ W $ na kusy 1 000 $ : Vyberte položku s maximálním $ p_i / w_i $ a vložte z něj co nejvíce. Pokud vám dojde, vyberte si další a dejte z něj co nejvíce. A tak dále. Implementace tohoto algoritmu vyžaduje seřazení seznamu $ p_i / w_i $ , což vyžaduje čas $ O (n \ log n) $ . Algoritmus, který popisujete, používá stejný trik jako v rychlém výběru ke zkrácení doby běhu na $ O (n) $ za cenu náhodného provedení algoritmu.

Navrhuji následující cestu k pochopení algoritmu:

1. Pochopte klasický chamtivý algoritmus pro zlomkový batoh.
2. Pochopte rychlý výběr.
3. Podívejte se, jak algoritmus, který citujete, kombinuje techniku rychlého výběru s chamtivým přístupem.

R je množina poměrů zisku / hmotnosti každého objektu , kde je uveden zisk a hmotnost objektů. A W je kapacita batohu .
Nyní Místo výběru náhodného prvku v 1 kroku můžeme použít střední vyhledávací algoritmus na najít medián v O (n) krát.
A pak můžeme udělat zbytek všech kroků.Analýza časové složitosti tedy bude –
        T (n) = T (n / 2) + O (n).
A jako řešení dostaneme O (n) . Řekněte mi, pokud něco není správně vysvětleno a chcete vědět něco víc.

V lineárním čase najdete střední položka z hlediska hodnoty na jednotku hmotnosti. Pak také v lineárním čase zjistíte, zda se vám do batohu vejdou všechny předměty, které jsou alespoň tak cenné v batohu. Pokud můžete, udělejte to a rekurzivně vyřešte tento problém u n / 2 položek s nižší hodnotou za předpokladu, že jste “ Už jsem batoh naplnil. Pokud nemůžete, můžete vyhodit n / 2 položky nižší hodnoty, a poté zkuste problém vyřešit znovu pouze pomocí položek n / 2 nejvyšší hodnoty.

Zde se opakuje T (n) = T (n / 2) + O (n) a máme T (n) = O (n) podle potřeby.

V řešení, které jste vložili: R je množina poměrů, zisk / hmotnost W je součet celé hmotnosti této sady , slouží k porovnání s kapacitou vašeho batohu. Podobně {pi / wi | pi / wi} představuje i-tý prvek zisk je k i-té hodnotě hmotnosti. Porovnáváme tuto hodnotu s náhodně vybranou r hodnotou a poté segregujeme na základě srovnání poměru. R1, R2, R3 jsou další podmnožiny nastaveného poměru v závislosti na tom, zda je poměr menší, stejný nebo větší než poměr střední prvek.

Podobně W1, W2, W3 jsou součty vah těchto sad.

Nyní vyberte vhodnou sadu řešení v závislosti na hodnotách poměru, jak je vysvětleno na začátku.