Hogy oldjam meg a következő matematikai/algoritmusbeli feladatot?

Kérdés:

- Hány (x, y)-t lehet összevonni? Tehát az általad leír számsor esetén ha (120, 220), (300, 100), (280, 90) => (700, 410) is játszik?

Mert akkor lényegében minden lehetséges kombinációt előre legyártanék, hogy meglegyen a lehetséges halmazom.

Majd addig futtatom a halmaz elemeit az adott pontra, míg meg nem találnám.

Távolságra meg ezt a matematikai képletet alkalmazhatod: [link]

#2...

Ott van fent 1 link, csak megkellene nyitni. -.-'

Van pár dolog, ami szerintem tisztázásra vár.

1) Amit a #2 is felhoz: milyen metrika szerint mérjük a távolságot? Van preferencia alulról/felülről közelítésre? (Mellesleg kedves #3, nem túl szép dolog nagyképűsködni. Ráadásul ha még az értő olvasás sem megy, és nincs igazad, akkor még vicces is)

2) A lista elemszáma véges? Van rá korlát, vagy X függvényében akarunk algoritmusidőt mérni?

3) Mit tudunk a számokról? Egészek, pozitívak, korlátosak?

Amennyiben nincs valamilyen sokat segítő megkötés, a feladat minden bizonnyal NP nehéz, valószínűleg NP-teljes is.

[link]

[link]

Ez a két probléma elég közeli rokonságot mutat a te feladatoddal, valószínűleg az egyikre vissza lehet vezetni nem túl nehezen.

Amennyiben konkrétan szükséged van egy algoritmusra, akkor vagy az első válasz brute force megoldása jöhet szóba, vagy valamilyen dinamikus programozási megoldás, amire a wiki linkeken találsz példát.