AlgoritmusKét egyenlő összegElőször egy egyszerűbb kérdésre válaszolunk: Melyik az a legnagyobb A érték, amire a megadott pálcákból összeállítható két A hosszúságú darab? A "részhalmaz adott összeggel" algoritmusnál leírtakból indulva első ötletünk lehetne a következő: Minden i-re meghatározzuk, hogy az a1, a2, ..., ai pálcikákat használva milyen (A,B) hosszúságú párok rakhatók össze, majd ezek közül i = N esetén megkeressük a legnagyobb olyat, amire A=B. Az A és B maximális értéke a pálcikák összhossza lehet, tehát ennek négyzetével arányos lépést végzünk minden i-re. Mind a lépésszámot, mind a memóriaigényt csökkenthetjük, ha a dinamikus programozás tömbjét nem csak egy egybites (igen/nem) érték tárolására használjuk. A módosított algoritmus legyen a következő: minden i-re és minden d-re meghatározzuk, hogy melyik az a leghosszabb A pálcika, amire igaz, hogy az első i pálcikából összeállítható egy A és egy A-d hosszú pálcika. f(i,d) = max{ A | az a1, a2, ..., ai pálcikákból összeállítható egy A és egy A-d hosszú pálcika} A feladat megoldása az f(N,0) hívás eredménye. Az f(i,d) értékét a következő lehetőségek közül a legnagyobb adja:
Három egyenlő összegAz előző ötletet kell finomítani: f(i,d1,d2) = Itt a maximumot már 8 eset közül kell kiválasztani, ennek részletei a mellékelt forráskódban megtalálhatók. ÁBRA!!! KódokErben Péter (java): szabalyos.java |