melyik számok összege a végeredmény?

Algoritmusok

Sziasztok!

Van sok szám és van egy végösszeg.
Azt kéne kiderítenem, hogy a végeredmény melyik számok összegéből adódhatott.
Tudna valaki segíteni?
Ha van neve a problémának, akkor már az is sokat segítene.

Üdv: redman

  • 6006 megtekintés

( sj | 2009. 04. 08., sze – 14:29 )

mar hogyne lenne neve! 'melyik számok összege a végeredmény?'.... Bocs, csak vicceltem.

SPAMtelenul - POP3 spamszuro szolgaltatas

( sha v | 2009. 04. 08., sze – 15:23 )

42 a nevezetes vegeredmeny?

--
"It all keeps adding up / I think I'm cracking up / Am I just paranoid? / I'm just stoned"
/Green Day - Basket Case/

( emberk | 2009. 04. 08., sze – 15:45 )

Érdekes. Elvileg nem visszafejthető, csak szűkíthető, speciális esettől eltekintve. Pl ha a végeredmény páratlan akkor nem lehet kettő páros szám összegének eredménye..... De ehhez azt is jó lenne tudni, hogy hány összeadás történt, vannak e a buliban negatív számok...... Az hogy van egy számhalmazod, és egy végösszeg az megfejthetetlen, egészen speciális esettől eltekintve.

De semmivel nem lesz előrébb. Ha van a számhalmazban 1-es akkor tuti, hogy egyik szám sem zárható ki, a szám értékéig. Ergo semmit sem szűkítettünk a rendszeren, tehát semmilyen megoldást sem adtunk a triviálison kívül. A trivialitás pedig nem megoldás jelen esetben.

( Prey1982 | 2009. 04. 08., sze – 16:39 )

Többféle algoritmus is létezik a problémádra.

Az első (és ami ismertebb): hátizsák probléma. Adott a hátizsák kapacitásának az a szám, ami neked a "részösszeg", a többi szám pedig
ami a hátizsákba megy. Előny: ha viszonylag kicsi a szám, akkor közel polinomiális, ha nagyon nagy, akkor bukta az algoritmus, mert a
futásidő a célszámtól függ.

A másik algoritmus:
Dinamikus programozással megoldható, és egy 1*(részösszeg) vektorba bele is fér.

Ez egyébként mi? ACM, algoritmusok kötprogram?

_de_, csak legfeljebb lassabb lesz, egyébként mit értesz megoldhatóság alatt?

egyedi: az egyik algorutmus akkor működik _hatákonyan_ ha a megadott számok egyenletesen távolságra vannak egymástól, a másik meg ha csomós, tehát mindkettő megold bármilyen ehetőséget, csak mindkettő ha véletlenül a másikat kapja _lassabb_ lesz

( pelz | 2009. 04. 08., sze – 18:01 )

Van egy biztos megoldás.

Pl.:
12 = 1+1+1+1+1+1+1+1+1+1+1+1

Ez igaz, de összeget kértek.
És a 12 = 12 kifejezésben nincs összeg. (hacsak így nem: 12 = 12 + 0)

Ebből a pongyola fogalmazványból nem derül ki, mi is a feladat valójában.

Van sok szám és van egy végösszeg.
Azt kéne kiderítenem, hogy a végeredmény melyik számok összegéből adódhatott.

Gondolatolvasónak kell lenni ahhoz, hogy kitalálja valaki mi köze a "sok számnak" a "végösszeghez". Mert a kérdésből ez nem derül ki.
Egyébként is, az állítás, hogy "van sok szám", olyan alapigazság, hogy ki sem kellett volna jelenteni. Mindenki tudja, hogy végtelen sok szám van.

ha nem vagy gondolatolvasó, akkor is:
_van_ sok szám, tehát nem te találsz ki, hanem meg van adva, tehát eg halmaz adott (de ez persze már csak egy tipp, lehet hogy lista, és akárhányszor szerepeljet egy szám az összegben, de nem hiszem)

pl: {1,2,2,10,pi,pi,0.5} és az összeg, tehát a "végeredmény": 1
ennek _megoldása_: {1}, (bárkit megkérdezel az 1 elemű összeg is összeg, mellesleg épp az általad említett megfontolás miatt), mégpedig jelen esetben az egyetlen megoldás, a 0.5+0.5 nem, mert csak egyszer szerepelhet

Mint már mondottam: "A van sok szám" állítás olyan nagy általánosság, hogy igazából nem mond semmit.
Számomra, egyáltalán nem azt mondja, (amit már te állítasz), hogy van egy véges darabszámú számhalmaz.
És a második mondatból sem derül ki, hogy az általa emlegetett "sok számból" kell összeállítani az összeget. Ezért merészkedtem csupa egyesből összerakni.

Az csak egy példa volt. Oda írtam elé, hogy "Pl."
Továbbá, mint mondottam, gratulálok, hogy te oly találékony vagy és át tudtad fordítani, a "van sok szám" kifejezést "adva van egy számhalmaz" kifejezésre.
Én szűk-látókörűen próbáltam a mondat eredeti értelme felől közelíteni. Meaculpa:)

( mrev | 2009. 04. 08., sze – 18:47 )

Úgy gondolom, ez egy hátizsák probléma, legalábbis, ha a megadott számok között nincsenek negatívok. A hátizsák probléma visszavezethető legrövidebb utak keresésére, az meg dinamikus programozással megy.
--
CCC3

( bitvadasz | 2009. 04. 08., sze – 19:18 )

Hány éves a kapitány?

(a neve a problémának)

Egy évig hány a kapitány - ez más tészta.

( Digit | 2009. 04. 08., sze – 22:24 )

mi a fene
hogy lehet errol ennyit irni?
vagy en nem ertem?
mert nem ertem
ha tenyleg arrol van szo h "melyik szamok osszegebol adodhatott", akkor csak meg kell keresni az eshetosegeket es kesz.
ha meg netan arra gondolt h: melyik szamok osszegebol adodott, azt meg honnan tudhatnank?
szol ezen kivul meg masrol is ez az egesz???
(bocs ha irtak mar ezt)

úgy halsz majd meg, mint Hamilton, aki eztet mondta anatómiai vizsgálata előtt:

"Ne találjátok meg köreimet!"

gy.k. ez a Hamilton nem hasonlít a francia focista Henryre, ennek esze is volt.

Ez tipikusan a legtöbb inputra SUBSET SUM.

Arra akarok célozni, hogy adott méretű input fölött bizonyos problémákra adott legtöbb algoritmus nagyon hosszú idő alatt* fog lefutni/befejeződni

*: soha a bükkös durva életbe' sem

De nehogy szakbarbárnak nézzenek, lehet, hogy mégsem bonyelm szempontból kérdezi a kolléga a feladatot, az is lehet, hogy számelméleti partíciók problémakörben óhajtotta volna föltenni a kérdéseit. (Az is egy szép, és baromi nehéz témakör).

Pl. dinamikus programozás/bruteforce során ha ismerjük a különböző partíciók számát, akkor elegendő ennyit megtalálnunk, aztán befejeződhet az eljárásunk futása...

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

( Deimos | 2009. 04. 09., cs – 08:29 )

Szerintem ez egy penzvaltas problema. Letezik ra algoritmus, de nem ad egyertelmu megoldast. Van olyan valtozata is amit ugy neveznek hogy optimalis penzvaltas. Ez annyiban ter el, hogy a leheto legkevesebb szambol kell meghatarozni az osszeget. Pl.: az osszeg 7, a szamok: 1,1,1,3,4 akkor a megoldasok a 1+1+1+4 illetve a 3+4. Az optimalis ilyenkor a 3+4.

--
"Az a szóbeszéd járja Amerikában, hogy két intelligens faj létezik a földön: emberek és magyarok." by Isaac Asimov

amennyiben pénzváltás problémaként tekintünk rá, bizonyos megközelítésben és input-osztályokra polinomiális (pl. Vízvári Bélára hivatkoznék, kellemes és teljesen kellemes rendszerek kulcsszavakat tartalmazó előadására). Ehhez persze kellene a topiknyitó által közölt néhány példainputot ismernem.

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne