εύρεση βέλτιστου αθροίσματος υποσυνόλου από σειρές θετικών ακεραίων

[panos78]

Καλησπέρα.

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

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

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

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

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

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

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

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

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

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

Επεξ/σία 30 Οκτωβρίου 2022 από panos78

[DhmDim]

Αλλο array και αλλο σειρα στα μαθηματικά.

 

Εχεις 2 λιστες με αριθμους και θες απο τη πρωτη να τσιμπησεις 5 νουμερα και απο τη δευτερη 3 ωστε να φτιαξεις το αθροισμα Σ οπως το περιγραφεις;

 

Βρισκεις τους 5 μικροτερους αριθμους στη πρωτη λιστα 

Και τους 3 μικροτερους στη δευτερη .

Το αθροισμα αυτων των 8 ειναι το ελαχιστο Σ που μπορεις να εχεις.

 

Ή το εκανες πιο πολυπλοκο στο μυαλο σου ή κατι δε καταλαβα εγω καλα.

 

 

 

Επεξ/σία 30 Οκτωβρίου 2022 από DhmDim

[panos78]

από την πρώτη λίστα συμπληρώνονται τα 5 πρώτα στοιχεία του αθροίσματος. και η δεύτερη λίστα συμπληρώνει τις τις 3 επόμενες θέσεις.

η συμπλήρωση, για κάθε στοιχείο του αθροίσματος χρησιμοποιεί την πλήρη λίστα.

Παράδειγμα: για τις 5 πρώτες θέσεις:

Στοιχείο αθροίσματος 1: Στοιχείο πρώτης λίστας 4

Στοιχείο αθροίσματος 2: Στοιχείο πρώτης λίστας 1

Στοιχείο αθροίσματος 1: Στοιχείο πρώτης λίστας 3

Στοιχείο αθροίσματος 1: Στοιχείο πρώτης λίστας 1

Στοιχείο αθροίσματος 1: Στοιχείο πρώτης λίστας 6

Αντίστοιχα και για τις επόμενες 3 θέσεις με τη δεύτερη λίστα.

Αθροίζεται η ομάδα των 5 στοιχείων και η ομάδα των 3 και δίνει το άθροισμα Σ το οποίο συγκρίνεται με τον τυχαίο αριθμό Χ.

Αν το Σ >= Χ τότε ο πρώτος συνδυασμός των 8 αριθμός που θα προκύψει είναι το ζητούμενο μου.

[DhmDim]

1 ώρα πριν, panos78 είπε

από την πρώτη λίστα συμπληρώνονται τα 5 πρώτα στοιχεία του αθροίσματος. και η δεύτερη λίστα συμπληρώνει τις τις 3 επόμενες θέσεις.

η συμπλήρωση, για κάθε στοιχείο του αθροίσματος χρησιμοποιεί την πλήρη λίστα.

Παράδειγμα: για τις 5 πρώτες θέσεις:

Στοιχείο αθροίσματος 1: Στοιχείο πρώτης λίστας 4

Στοιχείο αθροίσματος 2: Στοιχείο πρώτης λίστας 1

Στοιχείο αθροίσματος 1: Στοιχείο πρώτης λίστας 3

Στοιχείο αθροίσματος 1: Στοιχείο πρώτης λίστας 1

Στοιχείο αθροίσματος 1: Στοιχείο πρώτης λίστας 6

Αντίστοιχα και για τις επόμενες 3 θέσεις με τη δεύτερη λίστα.

Αθροίζεται η ομάδα των 5 στοιχείων και η ομάδα των 3 και δίνει το άθροισμα Σ το οποίο συγκρίνεται με τον τυχαίο αριθμό Χ.

Αν το Σ >= Χ τότε ο πρώτος συνδυασμός των 8 αριθμός που θα προκύψει είναι το ζητούμενο μου.

Είναι ακριβώς αυτό που σου απάντησα απλά διάβασα λανθασμένα ότι ζητούσες Σ <= Χ . Όπου έγραψα "μικρότερους" άλλαξε το με "μεγαλύτερους" και έχεις τη λύση . 

Δε χρειάζεται να μπλέξεις με υποσύνολα . 

[panos78]

Δεν ξέρω αν καταλαβαίνω σωστά τη λύση που προτείνεις.
Αυτό που ψάχνω είναι το άθροισμα γίνει για πρώτη φορά ΜΕΓΑΛΥΤΕΡΟ από το την τιμή η οποία είναι τυχαία, δηλαδή Σ >= Χ.
Θα προσπαθήσω να γίνω πιο περιγραφικός, μήπως μπορέσω να βγάλω άκρη.
Ας υποθέσουμε ότι οι δύο λίστες θετικών ακεραίων είναι οι παρακάτω:

var wh = [0, 8, 16, 25, 35, 46, 58, 71, 86, 102, 120, 140, 163, 188, 216, 247, 282, 321, 364, 412, 466, 526, 592, 666, 749, 841, 944, 1058, 1185, 1326, 1484, 1659, 1854, 2072, 2314, 2583, 2883, 3216, 3588, 4001, 4461, 4973, 5543, 6177, 6883, 7669, 8544, 9518, 10602, 11808, 13152, 14647, 16312, 18166, 20230, 22528, 25088, 27937, 31111, 34646, 38583, 42968, 47853, 53295, 59357, 66111, 73637, 82022, 91366, 101780, 113386, 126322, 140741, 156814, 174734, 194712, 216988, 241827, 269526, 300418, 334872, 373303, 416173, 463997, 517354, 576887];
var dp = [0, 32, 65, 101, 139, 181, 227, 277, 331, 392, 458, 531, 611, 700, 797, 905, 1024, 1154, 1298, 1457, 1632, 1824, 2037, 2271, 2528, 2812, 3125, 3470, 3849, 4267, 4727, 5234, 5792, 6406, 7083, 7827, 8647, 9549, 10542, 11635, 12838, 14161, 15619, 17222, 18987, 20930, 23068, 25421, 28010, 30860, 33996, 37448, 41248, 45429, 50032, 55098, 60673, 66811, 73567, 81003, 89190, 98202, 108123, 119046, 131072, 144312, 158890, 174943, 192619, 212084, 233519, 257127, 283127, 311763, 343305, 378049, 416322, 458484, 504934, 556109, 612494];

Το επόμενο δεδομένο είναι οι 8 θέσεις του αθροίσματος (σε εικόνα φαίνεται στη συνέχεια).

Τώρα ένα παράδειγμα.
Ας υποθέσουμε ότι Χ = 79.
O υπολογισμός πρέπει δίνει το άθροισμα:

Σ = 71+ 8 + 0 + 0 + 0 + 0 + 0 + 0 = 79 >= 79 true

ή ακόμα καλύτερα τις θέσεις (index) των τιμών από τις λίστες:

var result = [7,1,0,0,0,1,1,0],

Ελπίζω να εξήγησα επαρκώς τι ψάχνω. Η γλώσσα που προτίθεμαι να χρησιμοποιήσω είναι η Javascript.

Επεξ/σία 30 Οκτωβρίου 2022 από panos78

[archer100]

Αν καταλαβα καλα, κανεις τυχαιες δοκιμες αριθμων μεχρι να πετυχεις τον πρωτο συνδυασμο που θα δινει Σ>=Χ;

[panos78]

Όπως βλέπεις παραπάνω, ο συνδυασμός που θέλω να επιλέγεται παραπάνω δεν είναι ο πρώτος βάσει τυχαιότητας, αλλά αυτός που έχει τα περισσότερα μηδενικά (οι τα λιγότερα μη μηδενικά στοιχεία) ως στοιχεία του αθροίσματος, αναφορικά με την ομάδα των 5 και των 3 που έχω πει σχετικά και ως δεύτερο βήμα (αν υπάρχουν περισσότεροι του ενός συνδυασμοί από το προηγούμενο βήμα) εκείνος ο συνδυασμός που όταν αθροίζεις τις θέσεις (index) δίνουν το μικρότερο δυνατό άθροισμα.

Συνέχεια του παραπάνω παραδείγματος:

Και ο συνδυασμός: Σ = 16 + 8 + 8 + 8 + 8 + 32 + 0 + 0 = 80 >= 79 επαληθεύει τη συνθήκη Σ >= Χ αλλά έχει μόνο δύο μηδενικά στοιχεία ενώ ο συνδυασμός που επιλέχθηκε έχει 5 μηδενικά στοιχεία.

Λαμβάνοντας υπόψη τα παραπάνω, εκτιμώ ότι έτσι προκύπτει ο βέλτιστος συνδυασμός. Αυτό φυσικά μένει να αποδειχθεί ότι ο συλλογισμός μου είναι σωστός.

[Επισκέπτης]

φίλε αν επιτρέπεται η επανάληψη των στοιχείων δεν μιλάμε για συνδυασμούς (84 ανα 5 και 80 ανα 3) αλλά για μεταθέσεις στοιχείων οι οποίες είναι πολύ περισσότερες. 

Μπούρδα είπα....

επαναληπτική διάταξη 84 ανα 5 είναι....

Επεξ/σία 31 Οκτωβρίου 2022 από kremidi

[panos78]

Δεν γνωρίζω τι σημαίνει επαναληπτική διάταξη...

Η κάθε μια από τις 5 πρώτες θέσεις συμπληρώνεται αποκλειστικά από την πρώτη λίστα που έχει 86 στοιχεία (μαζί με το 0), οπότε φαντάζομαι ότι οι συνδυασμοί είναι 86 υψωμένο εις την πέμπτη.

Ομοίως η κάθε μια από τις επόμενες τρεις θέσεις συμπληρώνεται αποκλειστικά από τη δεύτερη λίστα που έχει 81 στοιχεία (μαζί με το 0), οπότε φαντάζομαι ότι οι συνδυασμοί είναι 81 υψωμένο εις τον κύβο.

Από εκεί και πέρα, υποθέτω ότι το σύνολο των συνδυασμών είναι το γινόμενο των δύο προηγούμενων.

Από την άλλη μεριά δεν ξέρω πως υπολογίζονται οι συνδυασμοί, αν η σειρά με την οποία εμφανίζονται οι αριθμοί στο άθροισμα είναι αδιάφορη ανά ομάδα αριθμών (5 και 3 αντίστοιχα). Για να γίνω πιο σαφής ο συνδυασμός [1,4,6,8,20] είναι ο ίδιος με τον συνδυασμό [20,8,6,4,1], οπότε ο πρώτος συνδυασμός δε χρειάζεται να προσμετρηθεί.

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

[virxen75]

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

var wh = [0, 8, 16, 25, 35, 46, 58, 71, 86, 102, 120, 140, 163, 188, 216, 
    247, 282, 321, 364, 412, 466, 526, 592, 666, 749, 841, 944, 1058, 1185,
     1326, 1484, 1659, 1854, 2072, 2314, 2583, 2883, 3216, 3588, 4001, 4461,
      4973, 5543, 6177, 6883, 7669, 8544, 9518, 10602, 11808, 13152, 14647, 
      16312, 18166, 20230, 22528, 25088, 27937, 31111, 34646, 38583, 42968, 
      47853, 53295, 59357, 66111, 73637, 82022, 91366, 101780, 113386, 126322,
       140741, 156814, 174734, 194712, 216988, 241827, 269526, 300418, 334872,
        373303, 416173, 463997, 517354, 576887];
var dp = [0, 32, 65, 101, 139, 181, 227, 277, 331, 392, 458, 531, 611, 700, 
    797, 905, 1024, 1154, 1298, 1457, 1632, 1824, 2037, 2271, 2528, 2812, 3125,
     3470, 3849, 4267, 4727, 5234, 5792, 6406, 7083, 7827, 8647, 9549, 10542, 11635,
      12838, 14161, 15619, 17222, 18987, 20930, 23068, 25421, 28010, 30860, 33996, 
      37448, 41248, 45429, 50032, 55098, 60673, 66811, 73567, 81003, 89190, 98202,
       108123, 119046, 131072, 144312, 158890, 174943, 192619, 212084, 233519, 257127,
        283127, 311763, 343305, 378049, 416322, 458484, 504934, 556109, 612494];

var X=79;
var new_wh = wh.filter(function(x) {return x <=X;});
var new_dp = dp.filter(function(x) {return x <=X;});
console.log(new_wh)
console.log(new_dp)

οπότε έχεις τους νέους πίνακες να βρεις αυτό που ψάχνεις

[0,  8, 16, 25,35, 46, 58, 71]
[ 0, 32, 65 ]

[Επισκέπτης]

3 ώρες πριν, panos78 είπε

Δεν γνωρίζω τι σημαίνει επαναληπτική διάταξη...

Η κάθε μια από τις 5 πρώτες θέσεις συμπληρώνεται αποκλειστικά από την πρώτη λίστα που έχει 86 στοιχεία (μαζί με το 0), οπότε φαντάζομαι ότι οι συνδυασμοί είναι 86 υψωμένο εις την πέμπτη.

Ομοίως η κάθε μια από τις επόμενες τρεις θέσεις συμπληρώνεται αποκλειστικά από τη δεύτερη λίστα που έχει 81 στοιχεία (μαζί με το 0), οπότε φαντάζομαι ότι οι συνδυασμοί είναι 81 υψωμένο εις τον κύβο.

Από εκεί και πέρα, υποθέτω ότι το σύνολο των συνδυασμών είναι το γινόμενο των δύο προηγούμενων.

Από την άλλη μεριά δεν ξέρω πως υπολογίζονται οι συνδυασμοί, αν η σειρά με την οποία εμφανίζονται οι αριθμοί στο άθροισμα είναι αδιάφορη ανά ομάδα αριθμών (5 και 3 αντίστοιχα). Για να γίνω πιο σαφής ο συνδυασμός [1,4,6,8,20] είναι ο ίδιος με τον συνδυασμό [20,8,6,4,1], οπότε ο πρώτος συνδυασμός δε χρειάζεται να προσμετρηθεί.

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

Ψαξε για σημειωσεις συνδιαστικης στο ιντερνετ και καλο διαβασμα.

Αν και το προβλημα σου φαινεται αρκετα απλουστερο. Αφου θετεις σαν ορο το αρθροισμα του διατακτικου αριθμου των στοιχειων να ειναι το μικροτερο δυνατο (min), σε ταξινομημενη λιστα που συμμετεχει το μηδεν, τοτε δεν εχεις παρα να παιρνεις το πρωτο μεγαλυτερο, απο το δωθεν στοιχειο,της καθε λιστας και ολα τα αλλα 0.

[Aggeluska]

On 30/10/2022 at 20:18, panos78 said:

Δεν ξέρω αν καταλαβαίνω σωστά τη λύση που προτείνεις.
Αυτό που ψάχνω είναι το άθροισμα γίνει για πρώτη φορά ΜΕΓΑΛΥΤΕΡΟ από το την τιμή η οποία είναι τυχαία, δηλαδή Σ >= Χ.
Θα προσπαθήσω να γίνω πιο περιγραφικός, μήπως μπορέσω να βγάλω άκρη.
Ας υποθέσουμε ότι οι δύο λίστες θετικών ακεραίων είναι οι παρακάτω:

var wh = [0, 8, 16, 25, 35, 46, 58, 71, 86, 102, 120, 140, 163, 188, 216, 247, 282, 321, 364, 412, 466, 526, 592, 666, 749, 841, 944, 1058, 1185, 1326, 1484, 1659, 1854, 2072, 2314, 2583, 2883, 3216, 3588, 4001, 4461, 4973, 5543, 6177, 6883, 7669, 8544, 9518, 10602, 11808, 13152, 14647, 16312, 18166, 20230, 22528, 25088, 27937, 31111, 34646, 38583, 42968, 47853, 53295, 59357, 66111, 73637, 82022, 91366, 101780, 113386, 126322, 140741, 156814, 174734, 194712, 216988, 241827, 269526, 300418, 334872, 373303, 416173, 463997, 517354, 576887];
var dp = [0, 32, 65, 101, 139, 181, 227, 277, 331, 392, 458, 531, 611, 700, 797, 905, 1024, 1154, 1298, 1457, 1632, 1824, 2037, 2271, 2528, 2812, 3125, 3470, 3849, 4267, 4727, 5234, 5792, 6406, 7083, 7827, 8647, 9549, 10542, 11635, 12838, 14161, 15619, 17222, 18987, 20930, 23068, 25421, 28010, 30860, 33996, 37448, 41248, 45429, 50032, 55098, 60673, 66811, 73567, 81003, 89190, 98202, 108123, 119046, 131072, 144312, 158890, 174943, 192619, 212084, 233519, 257127, 283127, 311763, 343305, 378049, 416322, 458484, 504934, 556109, 612494];

Το επόμενο δεδομένο είναι οι 8 θέσεις του αθροίσματος (σε εικόνα φαίνεται στη συνέχεια).

Τώρα ένα παράδειγμα.
Ας υποθέσουμε ότι Χ = 79.
O υπολογισμός πρέπει δίνει το άθροισμα:

Σ = 71+ 8 + 0 + 0 + 0 + 0 + 0 + 0 = 79 >= 79 true

ή ακόμα καλύτερα τις θέσεις (index) των τιμών από τις λίστες:

var result = [7,1,0,0,0,1,1,0],

Ελπίζω να εξήγησα επαρκώς τι ψάχνω. Η γλώσσα που προτίθεμαι να χρησιμοποιήσω είναι η Javascript.

Αυτό θες να το λύσεις σε κάποια γλώσσα προγραμματισμού ή με ψευδοκώδικα στο χαρτι; Ποια είναι η σχέση σου με την επιστήμη της πληροφορικής;

Ένας βέλτιστος τρόπος για να λύσεις το πρόβλημα είναι να το κανεις με την μεθοδολογία διαιρε και βασιλευε όπου σπας το προβλημα σε κομματάκια και λύνεις τα επιμέρους προβλήματα και μετα συνδιάζεις τις λύσεις.

Π.χ.: για Χ = 79, θα πάρεις την διάμεσο του wh και θα το συγκρίνεις με το 79, αν η διάμεσος ειναι μικρότερη από το 79 τότε θα πάρεις απο το wh απο 0 έως διάμεσος και απο αυτό θα πάρεις πάλι τη διάμεσο και θα επαναλαβεις την διαδικασία μέχρι ή διάμεσος ίσον 79 ή η υποακολουθία που έχεις να έχει μόνο ένα στοιχείο. Αυτο την πρώτη φορα θα καταλήξει στο 71. Μετά θα αφαιρέσεις 79-71 = 8 και θα επαναλαβεις την παραπανω διαδικασία για Χ = 8. θα κανεις το ιδιο και για τις τελευταιες 3 θεσεις μονο που εκει θα χρησιμοποιήσεις το dp αντι για το wd.

[virxen75]

χονδρικά ψάχνεις κάτι τέτοιο 

 

var wh = [0, 8, 16, 25, 35, 46, 58, 71, 86, 102, 120, 140, 163, 188, 216, 
    247, 282, 321, 364, 412, 466, 526, 592, 666, 749, 841, 944, 1058, 1185,
     1326, 1484, 1659, 1854, 2072, 2314, 2583, 2883, 3216, 3588, 4001, 4461,
      4973, 5543, 6177, 6883, 7669, 8544, 9518, 10602, 11808, 13152, 14647, 
      16312, 18166, 20230, 22528, 25088, 27937, 31111, 34646, 38583, 42968, 
      47853, 53295, 59357, 66111, 73637, 82022, 91366, 101780, 113386, 126322,
       140741, 156814, 174734, 194712, 216988, 241827, 269526, 300418, 334872,
        373303, 416173, 463997, 517354, 576887];
var dp = [0, 32, 65, 101, 139, 181, 227, 277, 331, 392, 458, 531, 611, 700, 
    797, 905, 1024, 1154, 1298, 1457, 1632, 1824, 2037, 2271, 2528, 2812, 3125,
     3470, 3849, 4267, 4727, 5234, 5792, 6406, 7083, 7827, 8647, 9549, 10542, 11635,
      12838, 14161, 15619, 17222, 18987, 20930, 23068, 25421, 28010, 30860, 33996, 
      37448, 41248, 45429, 50032, 55098, 60673, 66811, 73567, 81003, 89190, 98202,
       108123, 119046, 131072, 144312, 158890, 174943, 192619, 212084, 233519, 257127,
        283127, 311763, 343305, 378049, 416322, 458484, 504934, 556109, 612494];

var X=79;
var new_wh = wh.filter(function(x) {return x <=X;});
var new_dp = dp.filter(function(x) {return x <=X;});
console.log(new_wh);
console.log(new_dp);

var arrayLength1 = new_wh.length;
var arrayLength2 = new_dp.length;
// number = j1+j2+j3+j4+j5  +  i1+i2+i3

var array=[0,0,0,0,0,0,0,0]
var number=0
exit:
for (var i3 = 0; i3 <arrayLength2; i3++) {
    for (var i2 = 0; i2 <arrayLength2; i2++) {
        for (var i1 = 0; i1 <arrayLength2; i1++) {
            for (var j5 = 0; j5 <arrayLength1; j5++) {
                for (var j4 = 0; j4 <arrayLength1; j4++) {
                    for (var j3 = 0; j3 <arrayLength1; j3++) {
                        for (var j2 = 0; j2 <arrayLength1; j2++) {
                            for (var j1 = 0; j1 <arrayLength1; j1++) {
                                number=new_wh[j1]+new_wh[j2]+new_wh[j3]+new_wh[j4]+new_wh[j5]+new_dp[i1]+new_dp[i2]+new_dp[i3]
                                if (number>=X) {
                                    array=[j1,j2,j3,j4,j5,i1,i2,i3]
                                    console.log(new_wh[j1],new_wh[j2],new_wh[j3],new_wh[j4],new_wh[j5],new_dp[i1],new_dp[i2],new_dp[i3],"=",number)
                                    console.log("positions:",array)
                                    break exit
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

 

Επεξ/σία 1 Νοεμβρίου 2022 από virxen75

[panos78]

Σας ευχαριστώ όλους.

Από δοκιμές που έκανα με τον παραπάνω κώδικα, μέχρι το γέμισμα της 4ης θέσης, όλα φαίνεται ότι λειτουργούν χωρίς πρόβλημα.

Μόλις αρχίζει να γεμίζει η 5η θέση, αρχίζουν τα αγκομαχητά και φαίνεται ότι η ιστορία αρχίζει να ζορίζει.

Λογικό μου φαίνεται γιατί οι ελεγχόμενοι συνδυασμοί αυξάνονται γεωμετρικά.

Αναρωτιέμαι αν υπάρχει τρόπος ή μέθοδος να ξεπεραστεί;

[virxen75]

Στείλε την δοκιμή που έκανες και άρχισε να ζορίζει να δω αν μπορεί να γίνει κάτι.