permutacje? kombinacje? php c++ excel - help needed .. Opcje

[pwsmile]

Witam i proszę o pomoc ..

nie mogę rozgryźć następującej sprawy..

mam dane :

- x liczb (np.5 liczb i np. takie : 1 2 3 4 5 , ale może być też: 1 3 3 5 5)

- sumę którą chcę otrzymać z dodania którychś (obojętnie ilu) z danych liczb (np. suma=11)

.. i potrzebuję program / skrypt / arkusz excel, który powie mi jak Abel krowie, które liczby ze zbioru muszą być dodane, żeby utworzyły sumę jaką chcę.

Dla zbioru: 1 2 3 4 5 i danej żądanej sumy 11 byłyby to następujące możliwości:

1_2_3___5 (suma: 11)
__2___4_5 (suma: 11)

Dla zbioru: 1 3 3 5 5 i danej żądanej sumy 11 są 3 możliwości:

__3_3_5__ (suma: 11)
__3_3___5 (suma: 11)
1_____5_5 (suma: 11)

Nie jest ważne ile z liczb podanych w zbiorze złoży się na podaną sumę, jednak każda kolejna z liczb w zbiorze powtarzać się może tylko 1 raz (np. pierwsza liczba w ostatnim przykładzie (1) może byż brana pod uwagę tylko raz, czyli rozwiązaniem nie może być

1_1_1_1_1_1_1_1_1_1_1 (bo liczba 1 w zbiorze wystepuje tylko raz)

ale

liczba 5 - też w drugim przykładzie - powtórzyć się może 2 razy, bo tyle razy wystepuje w zbiorze


Super optymalnie byłoby, gdyby programik w przypadku nie znalezienia pasujących składników dających szukaną sumę, podał najbliższą możliwą kombinację w górę i najbliższą możliwą w dół ..

.. np jezeli żądaną sumą byłaby liczba 2, to mając dany zbiór jak w przykładzie drugim: 1 3 3 5 5 program nie znajdzie wprawdzie odpowiednika, bo suma żadnych ze składników w tym zbiorze nie daje liczby 2, ale wypisze:

1________ (suma: 1, reszta 1)
__3______ (suma: 3, reszta -1)
____3____ (suma: 3, reszta -1)

podobnie dla szykanej sumy 12 i tego samego zbioru: 1 3 3 5 5 pasujący odpowiednik nie zostanie znaleziony, jednak najbliższymi dodatnimi i ujemnymi wartościami będą:

1_____5_5 (suma: 11, reszta 1)
1_3___5_5 (suma: 13, reszta -1)
1___3_5_5 (suma: 13, reszta -1)




Jeżeli ktoś ma jakiś pomysł, lub może już nad czymś takim myslał i ma gotowca, byłbym wdzięczny za udostępnienie.

Pozdrawiam
pwsmile