Matematické Fórum
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
#1 26. 07. 2017 15:01 — Editoval dorwin (26. 07. 2017 15:10)
modifikovany problem batohu
Zdravim,
riesim tak trochu modifikovany problem batohu.
Totiz mam X predmetov o danych rozmeroch (sirka,vyska) a potrebujem to naukladat do batohu v tvare kruhu tak aby som zaplnil batoh co najviac. predmety ukladam na seba a vzdy je v jednej rade len jeden predmet.
a samozrejme nie vsetky predmety musim dat do batohu a vzdy budu orientovane na sirku.
Nechcem to riesit rekurziou. Viete ma prosim nasmerovat?
vdaka
Offline
#2 26. 07. 2017 23:35
Re: modifikovany problem batohu
Uloha je umiestnit max. pocet obdlznikov s fixnou orientaciou do daneho kruhu?
Ked hej, existuje rozumny algoritmus (vo vseobecnosti su ulohy tohto typu extra tazke, podmienka ze musia byt naukladane nad seba pomaha; rozumny tu znamena "dava presnu odpoved v polynomialnom case").
- 2 polkruhy, ukladas do nich obdlzniky podla rastucej sirky
- samozrejme kazdy obdlznik ide do stredu
- stav polkruhu komplet popises sirkou posledneho obdlznika ktory sa dotkol okraja a vyskou vsetkych obdlznikov na nom (vratane tohto), to ti da
- riesenie pre 1 polkruh: dynamicke programovanie (ak vies co to je); pre 
obdlznikov s celociselnymi vyskami do 
to ide v case 
- na konci mozes zobrat 2 polkruhy, zlepit ich dokopy a pridat jeden obdlznik do stredu ak sa da
Offline