Megoldás

Algoritmus

Két egyenlő összeg

Elő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:
  • ha nem használjuk az i. pálcikát
    f(i-1,d)
  • ha egyedül az i. pálcikát használjuk, vagyis d = ai
    ai
  • ha a magasabb "toronyra" rakjuk az i. pálcát
    f(i-1,d-ai)+ai
  • ha a kisebb "toronyra" rakjuk az i. pálcát, és az kisebb marad
    f(i-1,d+ai)
  • ha a kisebb "toronyra" rakjuk az i. pálcát, és az válik a nagyobbá
    f(i-1,ai-d)+d

Három egyenlő összeg

Az előző ötletet kell finomítani:

f(i,d1,d2) =
= max{ A | az a1, a2, ...,ai pálcákból összeállíthatók A, A-d1, A-d2 hosszú pálcikák (0<=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ódok

Erben Péter (java): szabalyos.java