Autor Zpráva
Rada99
Profil *
Ahoj, prosim radu. Potřebuji vyřešit tento úkol. Mám 2 lahve o objemu 1l, 0.5l a cílem je aby mi skript napočítal kolik lahví potřebuji když požadované celkové množství je 1.6l. Momentálně mám vyřešeno to tak že v cyklu procházím lahve a odečitam objem. Jenže výsledek není 100% protože dostanu 1x 1l a 2x0.5l a přitom bych potřeboval aby výsledek byl 2x1l
Giga
Profil
to je problém jedné podmínky. Cykly jsou zbytečnost ...
Keeehi
Profil
Jestli máš jen tyhle objemy, pak je řešení triviální.

$wantedVolume = 1.6;
$literBottles = floor($wantedVolume);
$halfLiterBottles = 0;
if($wantedVolume - $literBottles <= 0.5) {
    if($wantedVolume != $literBottles) {
        $halfLiterBottles++;
    }
} else {
    $literBottles++;
}

echo "$literBottles × 1l a $halfLiterBottles × 0.5l";
lionel messi
Profil
Riešil by som to cyklom nasledovne:

Vezmem si najväčšiu fľašu, vydelím celkový objem objemom väčšej fľaše (získam približný počet väčších fliaš, volajme ho x, možno bude potrebná korekcia - to zistím o chvíľu). Zistím si zvyšok po delení (dám si pozor na to, že trebárs v PHP mi operátor % vracia výsledok pre celočíselné delenie a vyhľadám si funkciu pre zvyšok po desatinnom delení). Skontrolujem, či ho dokážem umiestniť do menšej fľaše. Ak nie, potrebujem x + 1 väčších fliaš, ak áno, tak potrebujem x väčších a 1 menšiu fľašu.

PS: Bolo by fajn naprogramovať to tak, aby skript fungoval pre ľubovoľný počet fliaš (nielen dve).
Keeehi
Profil
Zajímavé by to bylo, pokud bys měl 5.1l a k dispozici 1l a 0.6l lahve. Minimální počet lahví je v takovém případě 6. Ovšem řešení je více. Můžeš použít 6x 1l nebo 4x 1l a 2x 0.6l. Pokud by se v takovém případě mělo preferovat řešení s ci nejmenším součtem objemů lahví, tak už to tak triviální nebude.
Rada99
Profil *
Pozor požadovány objem může být i jiný a take můžou být i jiné objemy lahví
Radek9
Profil
Rada99:
V [#4] ti lionel messi poměrně podrobně popsal algoritmus. Zkus to nejdřív sám napsat a pak se vrať, pokud máš problém s kódem. ;-)
Joker
Profil
Pokud jde o to jen zjistit nejnižší počet lahví, je řešení triviální:
Nejnižší počet lahví je: ceil(celkový objem / objem největší láhve).

Zahrnutím i menších lahví se nikdy nelze dostat na nižší počet.
Akorát to sice říká nejnižší počet lahví, ale ne jak optimálně nakombinovat jednotlivé druhy.

Keeehi:
Pokud by se v takovém případě mělo preferovat řešení s ci nejmenším součtem objemů lahví, tak už to tak triviální nebude.
Dokud budou jen dva druhy lahví a musím mít co nejnižší celkový počet, bude to pořád vcelku snadné.
Stačí místo „kolik se vejde plných větších lahví a pak dořešit zbytek“ vzít „o jednu méně než kolik se vejde plných větších lahví a pak dořešit zbytek“.

Algoritmus (značím objem k rozdělení = objem, objem větší lahve = ov, objem menší lahve = om):
1. Zbývající objem zo = objem.
2. Pokud zo > ov, přidám floor(zo / ov) - 1 větších lahví a příslušně snížím zo.
3. Pokud zo <= om, přidám 1 menší lahev a vrátím výsledek.
4. Pokud zo <= ov, přidám 1 větší lahev a vrátím výsledek.
5. Pokud zo <= 2 * om, přidám 2 menší lahve a vrátím výsledek.
6. Přidám 2 větší lahve a vrátím výsledek.
Keeehi
Profil
Joker:
V této konfiguraci to nefunguje
objem = 5,7
ov = 1
om = 0,9

Pokud jsem to správně propočítal, tak jsem se dostal až k 6, tedy 6 velkých lahví. Ovšem dá se to také vyřešit 3 velké a 3 malé. Zřejmě by to šlo nějak parametrizovat. Kolik lahví se musí ubrat je závislé na tom, jak poměr ov a om. Čím blíže k jedničce (objemy jsou skoro stejné) tím více se musí ubrat v bodu 2.


Jinak obecně - Tahle úloha bude spadat někam do oblasti bin packing problem, knapsack problem. Obecně to jsou NP-hard těžké úlohy, takže obecné řešení této úlohy může být stejně složité. Co by to mohlo zjednodušovat je fakt, že se jedná o tekutinu. Tudíž je možné si to rozsekat na malé jednotky, ovšem všechny stejně veliké. Tím pádem odpadá komplexita určení která položka má přijít do kterého kontejneru, jelikož všechny položky jsou si sobě ekvivalentní. NP-hard to tedy si nebude ale přímočarou implementaci řešení kde vstupem je objem k zabalení a jakkoliv velký seznam možných velikostí obalů bohužel hned nevidím.
Rada99
Profil *
děkuji za návody, zadani se pouprovilo asi na tu nejhorší variantu, že počt možných sklenic je různý ale už snad dám do kupy..
dík

Vaše odpověď


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm:

0