Ezt hogy lehet optimálisabban megoldani?
"Kedvenc táblás csokink kétféle kiszerelésben kapható. Az egyik A darab szegmensből áll, a másik B darabból. Mi összesen C darab szegmenst szeretnénk vásárolni.
Ha csak egész táblákat vehetünk és mindkét kiszerelésből korlátlan számban vásárolhatunk, akkor mennyi szegmensünk lehet maximum, ami még nem több C darabnál?
1 <= A, B, C <= 1000"
Pl.:
A = 5
B = 7
C = 13
Megoldás: 12
Magyarázat:
- vehetünk 2db B-t, de 2*7>13 és nem akarunk többet C-nél
- vehetünk 1db A-t és 1db B-t, ez 12 lesz, eggyel kisebb C=13-nál, potenciális megoldás
- vehetünk 2db A-t, ez 10 lesz, ez is egy potenciális megoldás, de az előzővel jobban járunk
- vehetünk 1db A-t vagy 1db B-t, de ezeknél jobban járunk a korábbi potenciális megoldással
- van még végtelen számú más lehetőség, de ezek mind nagyobbak C-nél
Megcsináltam rekurzívan mélységben-először kereséssel de már 30 körüli értékekre is percekig fut bizonyos esetekben és elvileg 1000 a maximum.
válasza:Én elindulnék a keresett számmal, majd leosztanám modulo az egyik számmal, majd az eredményt a másikkal. Ha nem jön ki 0 eredmény, akkor eggyel kisebb számra, majd megint eggyel kisebbre.
Példa
1. 13 mod 7 = 6 => 6 mod 5 = 1 => nem jó
2. 12 mod 7 = 5 => 5 mod 5 = 0 => jó
1-es köszi a választ, de nem egészen értem ez hogy adna jó megoldást.
Vegyünk pl. A=17, B=11, C=43-at. Itt 39 a jó megoldás.
39 mod 17 = 5, 5 mod 11 = 5
39 mod 11 = 6, 6 mod 17 = 6
Nem jött ki 0 egyikre sem.
Ki tudnád fejteni kicsit?
válasza:Ugy latom ez egy kozepiskolai feladat, itt nyilvan agyuval verebre a DFS. Tanitanak egyaltalan DFS-t kozepiskolaban?
A sima brute force megoldas 2 for loop meg egy maximum kivalasztas, azzal csinald, O(C^2) lesz a time complexity, par ms alatt le kell futnia a legrosszabb esetre is (1 1 1000).
Basszus túlbonyolítottam :D Működik köszi.
De egyébként mélységben kereséssel sem kellene lassúnak lennie nem?
válasza:Sokkal gyorsabbnak kell lennie a DFS-nek, ha jol van implementalva, de az mar DP terulet, olyat plane nem tanitanak kozepiskolaban.
A brute force O(C^2)/O(1) time/space, a DFS+DP O(C)/O(C).
DFS DP nelkul O(2^C)/O(C), te valoszinuleg ezt implementaltad, azert lassu mar kis ertekekre is.
válasza:Egy verzió C#-ban tetszőleges számú szegmensre. Azonos összegű részmegoldások közül mindig a legkisebb darabszámút tárolja el.
válasza:Én nem értem az itteni válaszokat... DFS meg DP... négyzetes sőt exponenciális futásidejű meg lineáris tárigényű megoldások?
Mi a francnak? Itt egyetlen for ciklusról van szó könyörgöm.
Ez valami általános iskolás feladat.
Nettó 5 sorban a megoldás (a többi csak sallang):
int a = 5;
int b = 7;
int c = 13;
int d = c;
for (int i = 0; i < c; i += a)
{
int rem = (c - i) % b;
if (rem < d)
{
d = rem;
}
}
Console.WriteLine("max szegmens: " + (c - d));
válasza:#9 ha nem erted a valaszokat, akkor erdemes lenne elolvasnod a kerdeseket.
Ugy jott fel a DFS, hogy a kerdezo azzal implementalta, konkretan benne van a kerdesben.
Aztan kerdezte, hogy "De egyébként mélységben kereséssel sem kellene lassúnak lennie nem?", igy jott fel a DP.
A brute force megoldas pedig mint legegyszerubb megoldas kerult szoba az elejen, ahhoz meg modulo sem kell.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!