Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
ahoj mam ulohu s loupeznikama
2 loupeznici odhadnou cenu predmetu ktere maji a chteji si je rozdelit napul
nacte se ze souboru poklad.in ceny predmetu na druhem radku a na prvnim pocet predmetu a do poklad.out se vypise na jeden radek indexy veci ktere dostane jeden z nich, pokud to neni mozne vypise se no
algoritmus by mel byt nasledovny:
secte se cena predmetu, jestli je delitelna dvema pak by mel byt algotitmus stejny jako u batohu
je tu prosim nekdo kdo by mi napsal jak ma na to vypadat cely zdrojak?
dekuju moc
Offline
Ahoj, problém dvou loupežníků je tzv. NP-úplným problémem.
Více se o této problematice můžeš dozvědět třeba zde: http://ksp.mff.cuni.cz/tasks/23/cook5.html
Neznám na tuto úlohu žádný efektivní algoritmus (tímto problémem jsem se příliš nezabýval, ale nemyslím si, že by nějaký efektivní algoritmus mohl existovat). Nejrychlejším správně pracujícím řešením je tedy zkoušení všech možností, což bude mít exponenciální časovou složitost.
Nabízí se algoritmus takový, že vstupní ceny setřídím sestupně a postupně tyto setříděné ceny přidávám tomu loupežníkovi, který má doposud menší součet cen, avšak tento postup je chybný, protože např. pro vstup 3 3 2 2 2 dá špatý výsledek (3+2+2 a 3+2).
Není mi jasné, jak bys to chtěl řešit stejně jako u problému loupežníkova batohu. Díky za objasnění, avšak myslím si, že ani tento postup nebude pracovat vždy korektně.
Offline