Ευρεση αθροισματος συνδυασμων

[adi32]

Υπαρχει καποιος ευκολος τροπος να μπορω να βρισκω αθροισματα καποιων συνδυασμων?

πχ εχω 20 νουμερα και θελω να δω ποια 6 απο αυτα μου κανουν αθροισμα 6352

[Krokodilos]

Υπαρχει καποιος ευκολος τροπος να μπορω να βρισκω αθροισματα καποιων συνδυασμων?

πχ εχω 20 νουμερα και θελω να δω ποια 6 απο αυτα μου κανουν αθροισμα 6352

Αν σε καθε αριθμο απο τους 20, αφαιρεσεις το 6352/6 τοτε εχεις ενα νεο σετ 20 αριθμων και το προβλημα σου αναγεται στο γνωστο NP-Complete προβλημα Subset_sum_problem.

Και αφου ειναι NP-Complete δεν υπαρχει γνωστος αλγοριθμος για τη γενικη λυση τετοιων προβληματων σε πρακτικο χρονο.

 

Βεβαια για πρακτικους σκοπους μπορει να σε ικανοποιησει ο παρακατω αλγοριθμος οπου μπορει να χειριστει γρηγορα σετ εως και 500 αριθμων για αριθμους που δεν ειναι πανω απο 2 δισεκατομμυρια.

Αλγοριθμος: Diophantine linear equation.

[smilefreeware]

Οι συνδυασμοί είναι 38760.

Νούμερο μικρό για αυτή την εποχή.

 

Πίνακας Α(20) για τους αριθμούς.

for n1=1 to 15

for n2=n1+1 to 16

for n3=n2+1 to 17

for n4=n3+1 to 18

for n5=n4+1 to 19

for n6=n5+1 to 20

if A(n1)+A(n2)+A(n3)+A(n4)+A(n5)+A(n6)=6532 then ......

next

next

next

next

next

next

 

Η απάντηση είναι ακαριαία , μηδέν χρόνος.

[adi32]

ευχαριστω παιδια

θα δοκιμασω να τα βαλω σε μια βαση σε Access