ACM RTK - 2. skupina

Polaganje plošč

Imamo pravokotni trikotnik, širok a enot in visok b enot. Dobili smo tudi več pravokotnih plošč in poznamo njihove velikosti: i-ta plošča je široka w_i enot in visoka h_i enot. Plošče bi radi zložili v trikotnik tako, da bo spodnja stranica plošče ležala na spodnjem robu trikotnika (ki ima dolžino a; glej sliko spodaj), zgornje levo oglišče plošče pa bo ležalo na hipotenuzi trikotnika. Plošč ne smemo vrteti tako, da bi stranica w_i prišla po višini, h_i pa po širini. Poleg tega se plošče ne smejo prekrivati ali štrleti ven iz trikotnika, lahko pa se dotikajo. Naslednja slika kaže primer takega trikotnika, v katerega smo položili pet plošč:

Opiši postopek (ali napiši program ali podprogram, če ti je lažje), ki v okviru teh omejitev poišče največje možno število plošč, ki jih je mogoče položiti v trikotnik. Kot vhodne podatke tvoj postopek dobi velikost trikotnika (a in b), število plošč n in njihove dimenzije w₁, h₁, w₂, h₂, ..., w_n, h_n. Utemelji, zakaj je število plošč, ki ga najde tvoja rešitev, res največje možno.