Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Alg. Sve kombinacije cija suma daje zadati broj ?

[es] :: Art of Programming :: Alg. Sve kombinacije cija suma daje zadati broj ?

[ Pregleda: 4094 | Odgovora: 4 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

urosk
BG

Član broj: 28668
Poruke: 41
*.sbb.co.yu.



Profil

icon Alg. Sve kombinacije cija suma daje zadati broj ?16.02.2005. u 08:28 - pre 202 meseci
Treba mi algoritam koji daje sve kombinacije iz odredjenog skupa brojeva ciji je zbir jednak nekom unapred zadatom broju,
recimo zbir koji trazim je 20 a moguci brojevi su iz skupa 1, 3, 4, 5, 10, 11, 15.... trebaju mi sve kombinacije bilo kog reda npr (15,1,4) (10,4,5,1) (11,4,5) (15,5)...
 
Odgovor na temu

urosk
BG

Član broj: 28668
Poruke: 41
*.sbb.co.yu.



Profil

icon Re: Alg. Sve kombinacije cija suma daje zadati broj ?16.02.2005. u 10:39 - pre 202 meseci
Nista, uradjeno je.
 
Odgovor na temu

Alef
Viktor Kerkez
Novi Sad

Član broj: 505
Poruke: 188
*.041net.co.yu.



Profil

icon Re: Alg. Sve kombinacije cija suma daje zadati broj ?16.02.2005. u 11:43 - pre 202 meseci
Pošto tražiš samo algoritam, evo jedna mogućnost u Python-u.

Code:

from copy import copy

lista = []        # pomocna lista
kombinacije = []    # lista sa kombinacijama

def insert(lista):
    """ Proverava da li se ovaj *skup* brojeva koji prosledjujemo
    funkciji u obliku liste *lista* vec nalazi u listi *kombinacije* """ 

    for i in kombinacije:
        if set(i) == set(lista):  # set pretvara liste u skupovni tip
            return
    kombinacije.append(copy(lista))



def komb(sum, tren, skup):
    """
    sum  - suma koju trazimo
    tren - trenutna suma
    skup - skup brojeva koji dolazi u obzir za sumiranje
    """
    
    for i in skup:
        lista.append(i)
        tren += i
        if tren == sum:
            insert(lista)
            lista.pop()
            return
        elif tren > sum:
            lista.pop()
            return
        else:
            komb(sum, tren, skup)
            tren -= i
            lista.pop()



if __name__ == '__main__':
    sum = 20
    skup = [1, 3, 4, 5, 10, 11, 15]
    komb(sum, 0, skup)
    print kombinacije
 
Odgovor na temu

urosk
BG

Član broj: 28668
Poruke: 41
*.sbb.co.yu.



Profil

icon Re: Alg. Sve kombinacije cija suma daje zadati broj ?17.02.2005. u 08:26 - pre 202 meseci
Da, resenje je slicno.
 
Odgovor na temu

Genie_1984
Novi Sad

Član broj: 61150
Poruke: 93



+1 Profil

icon Re: Alg. Sve kombinacije cija suma daje zadati broj ?23.11.2009. u 23:30 - pre 144 meseci
Ima li neko rešenje ovog problema ali u C-u?

[Ovu poruku je menjao Genie_1984 dana 24.11.2009. u 00:43 GMT+1]
 
Odgovor na temu

[es] :: Art of Programming :: Alg. Sve kombinacije cija suma daje zadati broj ?

[ Pregleda: 4094 | Odgovora: 4 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.