[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Zosto zadacata nakit od navedeniot link ne pominuva so dinamicko programiranje  XML
Forum Index » Други натпревари
Author Message
stoki97



Joined: 18/02/2015 15:20:59
Messages: 9
Offline

Zadacata Nakit od 2015 J Припреми ден 3 sto moze da se najde na ovoj link
http://mendo.mk/algoritmi/Task.do?competition=150&id=255.

Nemie jasna zosto pominuva so greedy resenie a so DP(dinamicko programiranje) resenie ne pominuva.

Ova e resenieto za koe pominuva



a ova e resenieto kade sto pagja na runtime


Prasanjeto mi bese zosto zadacata e napravena samo da se resava so greedy approach a ne kako sto treba.
Ova go sogledav koga vidov deka vo zadacata pisuva da se najdi optimalnoto resenie kade sto ke ima minimalna razlika pomegju dvete grupi od nakiti no za dolniot slucaj ako odime po greedy resenieto(za koe pominuva 10/10) ke bide
14 12 10 20 22 ====> greedy (22 + 12 + 10 = 44 i 20 + 14 = 34 sto ke ispecati (34 44) no treba da bide (10 + 12 + 14 = 36 20 + 22 = 42 ) sto znaci pagja na ovoj slucaj no 10/10 pominuva na od MENDO slucaite sto ne mie jasno ....)
dodeka so DP resenieto si pecati najoptimalnoto grupiranje (36 42) no pagja na runtime za 4 slucai sto ne mie jasno zosto vaka e postavena zadacata.
despotovski01



Joined: 23/02/2014 14:36:12
Messages: 37
Offline

Задачата е наменета да се реши со динамичко програмирање, само што твоето решение го надминува меморискиот лимит (пресметај ги димензиите на dp матрицата и лесно ќе се увериш во тоа).
За да се надмине овој проблем, клучно е да се увиди кои податоци не треба да ги чуваме. За да пресметаме произволен елемент од матрицата dp[i][j], нас ни требаат само вредностите од редот i-1, сите останати редици не ни играат улога, од што може да се заклучи дека во еден момент нам ни е потребно да чуваме само 2 редици од матрицата (претходната редица и таа што во сегашниот момент ја пресметуваме), што многу ни ја намалува меморијата.
 
Forum Index » Други натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team