Autor Zpráva
pE eLL
Profil
ahoj
narazil sem takovy matematicky problemek a zajimalo by me jestli nekdo nevite jak na to

modelova situace:

1, mam knihovnu a vni mnoho policek (dejme tomu ze je jich tolik ze je nikdy nezaplnim)
2, do jedne policky se vejdou knihy o urcitem poctu stran (dejme tomu treba 1000 stran/policka)
3, jednou tydne mi dovezou nejaky pocet knih
4, u kazde knihy neni problem zjistit jeji pocet stran
5, potrebuji pomoci nejakych kombinaci nebo cehokoli jineho knihy co nejusporneji zaradit do policek
tzn dat do prvni policky takovou kombinaci knih aby se strankami blizili co nejblize 1000 (kapacita policky). a potom vzit zbytek knih a opet znej udelat nejvhodnejsi kombinaci na dalsi policku atd atd az se vsechny knihy rozdeli

ma nekdo nejaky napad jak na to??? je tohle v php vubec mozne udelat - pokud ne vsem by to slo???
za jakoukoli radu budu vdecny
BaTeCzKo
Profil
pE eLL
A k čemu to je?
thingwath
Profil
Máš konečný počet knih, tedy počet jejich kombinací je též konečný, máš i jasně rozhodnutelné pravidlo pro cílový stav -- co nejméně zabraných polí v knihovně. Tedy úloha podle všeho řešitelná je, ale otázka je, jak efektivně :-)
WanTo
Profil
Zkus se podívat na Korespondenční seminář z programování. Bývají tam podobné úlohy, projdi si jejich archiv a snad něco zajímavého najdeš.
pavel prochazka.zde.cz
Profil *
no napadu je spoustu.... Vezmi si prvni knihu , druhou atd dokud nebude hodnota tech 1000 stran. pokud se prekroci, tak si dej ty knihy bokem a pokracuj dal. Ale jeste nez pridas dalsi hnihu do druhe policky tak skontroluj zda by jeste nevesla na volne misto te prvni policky. Tak dokoncis druhou policku a zacni zaplnovat treti policku a pokazde zkontroluj zda kniha nevejde jeste na predchozi policky, pokud ne tak ji dej na tu treti. Kodud se stane ze se treba prvni policka zaplni treba na treba 95% tak tuto policku uz vyradit se seznamu to jen proto aby se to triheni urychlilo. To jeden napad a vychazi z toho jak by to delal v realu asi clovek :)
thingwath
Profil
http://www.cs.ucsb.edu/~suri/cs130b/BinPacking.txt

Možností je spousta, je to volba mezi složitějším algoritmem na výpočet a horším (méně optimálním) výsledkem. Problém je každopádně označován jako těžký :-)
pE eLL
Profil
WanTo: lol nektere ulohy me vazne pobavily - de videt ze timhle nekdo zije :)

pavel: tenhle postup me uz taky napadl a pokud nebude nic jineho tak ho taky pouziju - diky. nicmene mi slo spise o ten postup nejlepsi a to pomoci tech kombinaci .
pE eLL
Profil
thingwath: diky moc tohle vypada velmi zajimave....uvidim kolik ztoho pochopim.
WanTo
Profil
pE eLL
Jo jo, matfyzáci jsou úchylní na hrochy :-)
Toto téma je uzamčeno. Odpověď nelze zaslat.