υποσύνολο απο integer array με συγκεκριμένο άθροισμα

[timkoni]

Καλησπέρα,

Έστω ότι έχουμε ένα integer array.

 

Για παράδειγμα : (3 4 1 6 5 4 12 13 7 8)

 

Και έχουμε τη μεταβλητή n = 9

 

Πώς μπορώ να βρώ όλους τους συνδυασμούς υποσυνόλων απο το array που να έχουν άθροισμα n;

 

ΠΧ.  --> (3 4 1 6 5 4 12 13 7 8)

 

--> 4,5 = 9

-->  5,1,3 = 9

--> 8,1 = 9

--> .....

 

 

 

 

[Dinos_12345]

Εγώ πρώτα θα έβρισκα τις δυάδες. Δηλαδή θα έπαιρνα ένα ένα τα στοιχεία και θα τσέκαρα αν σε συνδυασμό με κάποιο άλλο κάνει τόσο. Αν ναι τότε θα εμφάνιζε τους αριθμούς. Μετά θα πήγαινα και θα έπαιρνα 2 στοιχεία και θα τσέκαρα αν υπάρχει 3ο που να κάνει τόσο με αυτά τα 2 που ήδη έχω. You get the idea.

[gon1332]

Υπάρχει ο προφανής τρόπος με brute-force.

Σε αυτόν ξεκινάς από έναν αριθμό, οπότε αν το μέγεθος του συνολου είναι Ν, έχεις Ν-1 αριθμούς να επιλέξεις για να αθροίσεις. Από εκεί και πέρα, όσο το άθροισμα δε ξεπερνά το n, συνεχίζεις με αυτά τα μονοπάτια. Δεντράκια δηλαδή.

 

Με μία γρήγορη σκέψη μπορείς να χρησιμοποιήσεις δυναμικό προγραμματισμό και να αποθηκεύσεις τα αποτελέσματα κάποιων μονοπατιών ώστε να τα έχεις ήδη υπολογισμένα αν τα ξαναχρειαστείς.

[defacer]

Το σύνολο όλων των υποσυνόλων του πίνακα που έχεις ονομάζεται power set. Οπότε η ευθεία λύση είναι να υπολογίσεις τα μέλη του power set και με το που υπολογίζεις ένα ελέγχεις και αν ικανοποιεί τη συνθήκη που θέλεις. Το πρόβλημα εδώ είναι πως αν ο πίνακάς σου έχει K στοιχεία, το powerset περιέχει 2^Κ στοιχεία (υποσύνολα). Αυτό σημαίνει ότι τα Κ για τα οποία μπορείς πρακτικά να βρεις τη λύση είναι μικρά, ας πούμε μέχρι Κ = 20.

 

Μπορείς να δεις το πρόβλημα και από άλλη οπτική. Πρόκειται για το subset sum problem, που όπως είναι λογικό επίσης απαιτεί 2^Κ βήματα για να υπολογίσεις το ζητούμενο. Όμως είναι δυνατό χρησιμοποιώντας τεχνικές dynamic programming να φτάσεις στη λύση πολύ γρηγορότερα (και πάλι όμως, το Κ δε μπορεί να πάει πολύ μακριά γιατί ο,τι κι αν κάνεις τα μαθηματικά είναι εναντίον σου). Άμα βάλεις στο google "subset sum dynamic programming" θα βρεις πολύ υλικό.

Επεξ/σία 8 Φεβρουαρίου 2016 από defacer

[k33theod]

Θα βοηθούσε ίσως λίγο αν αφαιρούσες ότι είναι >= του n, τα 0 αν υπάρχουν και γενικά ότι μπορεί να μικραίνει την λίστα είναι όφελος.

 

Επίσης αν κάνεις τη λίστα SORT ίσως βοηθάει εννοώ πχ όταν δοκιμάζεις συνδυασμούς που ξεκινάν με 4 και είναι 4+5 =9 δεν χρειάζεται να ψάξεις για 4+6 ή 4+8. Ξεκινώντας κατόπιν από τους μικρούτερος και βλέποντας π.χ ότι το άθροισμα των 4 μικρότερων αριθμών ξεπερνά το n αυτό σημαίνει ότι δεν χρειάζεται να ψαξεις για 4δες αλλά για 2αδες και 3αδες.

 

Επίσης ίσως βοηθάει να γίνει γρηγορότερα η δουλειά η τεχνική με το σπάσιμο της λιστας σε 2.

[defacer]

^ Αυτά τα κόλπα είναι όντως πολύ χρήσιμα γενικά γιατί μειώνουν το Κ που όπως είπαμε είναι μείζονος σημασίας.

 

Βεβαίως υπόψη ότι αν γίνει η δουλειά με dynamic programming δε χρειάζεται να κάνεις κάτι τέτοιο σαν "σπέσιαλ επεξεργασία" γιατί ο αλγόριθμος θα απορρίπτει επιτόπου όλες τις περιπτώσεις που δε μπορούν να οδηγήσουν σε λύση.

[gon1332]

^ Αυτά τα κόλπα είναι όντως πολύ χρήσιμα γενικά γιατί μειώνουν το Κ που όπως είπαμε είναι μείζονος σημασίας.

 

Βεβαίως υπόψη ότι αν γίνει η δουλειά με dynamic programming δε χρειάζεται να κάνεις κάτι τέτοιο σαν "σπέσιαλ επεξεργασία" γιατί ο αλγόριθμος θα απορρίπτει επιτόπου όλες τις περιπτώσεις που δε μπορούν να οδηγήσουν σε λύση.

Ή θα λαμβάνει έτοιμα αποτελέσματα από περιπτώσεις που έχει υπολογιστεί ένα μερικό άθροισμα.

[k33theod]

Εγώ τα αναφέρω γιατί εκτιμώ δεν ξέρει δυναμικό προγραμματισμό (ούτε εγώ ξέρω) ούτε πιστέυω είναι κάτι που μαθαίνεται ώς του Αγ Βαλεντίνου.

[albNik]

Δεν υπαρχει μη-brute force τρόπος εφόσον θες να απαριθμήσεις ολα τα υποσύνολα που εχουν το συγκεκριμένο άθροισμα.

Αν εχεις π.χ. 100 στοιχεια (2^100 υποσύνολα) και το ενα δισεκατομυριοστο τους (2^70) να ικανοποιεί τη συνθήκη ειναι τεράστιος αριθμος.

 

Γρήγορα μπορεις να βρεις το αριθμο των υποσυνολων.

Για το παραδειγμα σου (οταν δεν εχουμε επαναλήψεις αριθμών) [3 4 1 6 5 4 12 13 7 8] και αθροισμα 9 ο αριθμος αυτος ειναι ο συντελεστης του x⁹ στο παρακάτω

(x³+1)(x⁴​+1)(x¹​+1)...(x⁸​+1). Μπορεις να φτιαξεις ενα προγραμμα να το υπολογίζει.

[M2000]

Μια προσπάθεια σε Μ2000. Τα καταφέρνει το καψερό.

[defacer]

Ορίστε μια λύση dynamic programming σε C#: http://ideone.com/3o8hM5

 

Υπάρχουν μερικά πράγματα που επίτηδες έκανα κάπως εξεζητημένα και μερικά που έκανα έτσι λόγω τεμπελιάς (GetHashCode() { return 0; } ), βασικά με σκοπό να κινήσω περισσότερο το ενδιαφέρον. Enjoy!

[M2000]

Site: ΣεΜ2000

 

 

Αποτελέσματα:

Σύνολο  1, 3, 4, 6, 5, 4,12, 13, 7, 8

001.   1,   4,   4 

002.   1,   8 

003.   3,   6 

004.   1,   3,   5 

005.   4,   5 

 

 

Αποτελέσματα:

Σύνολο 1, 1, 1, 3, 3, 3, 4, 5, 1, 2

001.   1,   1,   1,   3,   3 

002.   1,   2,   3,   3 

003.   1,   3,   5 

004.   1,   1,   2,   5 

005.   1,   1,   3,   4 

006.   1,   1,   1,   2,   4 

007.   3,   3,   3 

008.   4,   5 

009.   2,   3,   4 

[exarhis]

 Για να το κάνω αυτό θα έκανα brootforce όπως εξηγεί ο 

gon1332

και τα αποτέλεσμα από όλες τις πράξεις θα τα καταχωρούσα στη DB. Έτσι μετά θα έκανα SELECT τις rows που έχουν σαν αποτέλεσμα το 9.

[panos78]

Καλησπέρα.

Συγνώμη που ανακινώ αυτό το παλαιό θέμα, αλλά θα ήθελα τα φώτα σας σχετικά με το πρόβλημα που έχω.

Περιγράφω, εν συντομία...

Έχω δύο σειρές (arrays) θετικών ακεραίων. Η μια σειρά έχει 85 στοιχεία και η δεύτερη 80 στοιχεία. Το πρώτο στοιχείο σε κάθε σειρά είναι το μηδέν.

Ταυτόχρονα έχω ένα άθροισμα Σ με 8 στοιχεία:

Σ = Α + Β + Γ + Δ + Ε + Ζ+ Η + Θ

Τα στοιχεία Α έως Ε λαμβάνουν τιμές από τη σειρά με τα 85 στοιχεία και τα στοιχεία Ζ έως Θ λαμβάνουν τιμές από τη δεύτερη σειρά με τα 80 στοιχεία.

Τώρα το άθροισμα Σ θέλω να το συγκρίνω με μια τυχαία τιμή Χ θετικού ακεραίου.

Αν η σύγκριση βγάζει το Σ ίσο ή μεγαλύτερο από το Χ, τότε αναζητώ το πρώτο άθροισμα που πληρεί αυτή την προϋπόθεση.

Το ερώτημά μου προς εσάς είναι αν αυτό το πρόβλημα εντάσσεται σε αυτή την ιστορία με τα υποσύνολα και αν αυτό ισχύει με ποια βήματα θα μπορούσε να επιλυθεί;

Ευχαριστώ εκ των προτέρων για τυχόν απαντήσεις σας και είμαι στη διάθεσή σας για τυχόν διευκρινήσεις.