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
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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)

dorwin
Zelenáč
Příspěvky: 1
Reputace:   
 

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

Xellos
Příspěvky: 504
Škola: MFF CUNI, Bc. (13-16)
Reputace:   33 
 

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 $N$ obdlznikov s celociselnymi vyskami do $2R$ to ide v case $O(N^2R)$
- na konci mozes zobrat 2 polkruhy, zlepit ich dokopy a pridat jeden obdlznik do stredu ak sa da

Offline

 

#3 31. 07. 2017 15:56

mracek
Příspěvky: 70
Reputace:   
 

Re: modifikovany problem batohu

↑ dorwin:
Pokud je muzes skladat jen na sebe a nahore dole se to zuzuje, tak staci cisla seradit a na stridecku davat nahoru a dolu.

5 2 3 4 1 6
1 2 3 4 5 6
1 3 5 | 6 5 2

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson