| Autor | Zpráva | ||
|---|---|---|---|
| Klobás Profil * |
Ahoj,
potřeboval bych poradit s následujícím algoritmem. Mám řadu čísel a potřebuji zjistit počet skupin, do kterých se čísla vejdou. Je maximální limit na skupinu 30. Mám čísla např [25, 6, 25, 25] // budou 4 skupiny, protože 25 a 6 je víc než 30, takže číslo 6 bude v samostatné skupině Další příklady [10, 10, 9, 1] // 3 skupiny [10, 10, 10, 1] // 4 skupiny Poradí někdo? Nepotřebuji vědět, jak budou čísla v jednotlivých skupinách, stačí mi počet skupin. Tak jsem na to nějak přišel, ale kdyby někdo napsal něco smysluplnějšího, budu rád. $nums = [25, 6, 25, 25];
$groups = 1;
$temp = 0;
foreach ($nums as $n)
{
$temp += $n;
if ($temp > 30) {
$temp = 0;
$groups++;
}
}
echo $groups;Tak nic, je to blbě, jsou to 3 skupiny, měly být 4. |
||
| juriad Profil |
#2 · Zasláno: 16. 8. 2022, 09:21:22
Tato úloha je známá jako "bin packing" (en.wikipedia.org/wiki/Bin_packing_problem) a je NP úplná. V plné obecnosti nejspíš neexistuje lepší algoritmus než takový, který zkouší všechny možnosti. Jeden cyklus ti stačit nebude.
Chybu v tom svém algoritmu máš v tom, že pokud $temp překročí 30, tak to číslo by se mělo použít v nové grupě:
$temp = $n; Když si to spustíš na tomto vstupu, dodá ti tvůj algoritmus mnohem větší výsledek, než je optimální. 1 30 2 29 3 28 4 27 5 26 ... 15 16 |
||
| Keeehi Profil |
#3 · Zasláno: 16. 8. 2022, 09:24:28
Když říkáš řadu, znamená to, že je důležité pořadí? Protože to slovo řada implikuje, nicméně v takovýchto úlohách na pořadí většinou nezáleží. Pro ilustraci, kdyby na pořadí záleželo, řada [10, 1, 10, 9] by byla ve 4 skupinách. Pokud na pořadí záleží, šel by s malou úpravou použít ten tvůj algoritmus.
Obávám se ale, že na pořadí nezáleží. V takovém případě se z toho stává optimalizační úloha jejíž řešení není triviální. Navíc složitost roste velmi rychle s každým přidaným prvkem do množiny. Tento problém má svoje jméno Bin packing problem a najdeš na toto téma spoustu článků. Existují algoritmy, které dokáží najít optimální řešení. Ale doba výpočtu velmi rychle roste čím je množina větší. Jaká bude typická velikost tvého problému a jaká maximální? Pak existují algoritmy, které jsou jednodušší, mnohem rychlejší, zvládnou větší množiny a ve velké většině případů najdou i to optimální řešení. Ale není to garantované a občas vrátí o něco horší než optimální výsledek. Ale zase je to lepší než "hloupě" brát jeden prvek za druhým a bez nějaké logiky je skládat za sebou do boxu a když se už nevejdou, tak přejít na nový box. |
||
| Klobás Profil * |
#4 · Zasláno: 16. 8. 2022, 13:01:52
juriad:
Díky s nastavením $temp-u na $n to konečně funguje. Díky za odkaz, mrknu se na to, ale nevypadá to zcela snadně. Jinak nejde o optimálnost, opravdu mi stačí počet skupin a nedávat do skupiny nejmenší čísla tak, aby vyšel počet skupin co nejmenší, to není cíl. Keeehi Ahoj, díky i tobě. Nevím jak to myslíš, jestli záleží na pořadí, ale tvůj příklad s [10,1,10,9] ve 4 skupinách nebude, musí být v jedné protože součet se nedostane přes 30, takže jsou v 1 skupině. Výsledný skript (poupravený poznámkou od juriada) <?php
$nums = [25, 6, 25, 25];
$groups = 1;
$temp = 0;
foreach ($nums as $n)
{
$temp += $n;
if ($temp > 30) {
$temp = $n;
$groups++;
}
}
echo $groups;Keehi pokud jsi nemyslel tou malou úpravou mého skriptu, co jsi myslel? Jinak defakto se jedná o skupiny produktů a cílem má být, ne co nejoptimálnější složení (nejmenších k sobě), aby to bylo nejkompaktnější, to by byl zas problém v logistice (to je zase jiný problém a už ne náš). Cílem bylo, aby to vyšlo tak jak jsem psal nahoře. |
||
|
Časová prodleva: 2 roky
|
|||
0