Υπολογισμός συνδυασμών αθροισμάτων

[adi32]

Εχω πχ 3 αριθμούς και Θέλω τους πιθανους συνδυασμους για ενα συγκεκριμένο αθροισμα  

πχ 110,  200 , 120  ωστε να έχουν αθροισμα 1000

110χ8 + 120χ1=1000

200χ5=1000.....

Υπαρχει καποιο online εργαλειο ή κατι σε  excel για κάτι τέτοιο?

Επεξ/σία 20 Απριλίου 2022 από adi32

[archer100]

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

Εχω πχ 3 αριθμούς και Θέλω τους πιθανους συνδυασμους για ενα συγκεκριμένο αθοροισμα  

πχ 110,  200 , 120  ωστε να έχουν αθροισμα 1000

110χ8 + 120χ1=1000

200χ5=1000.....

Υπαρχει καποιο online εργαλειο ή κατι σε  excel για κάτι τέτοιο?

Μαλλον οχι. Μονο με προγραμματισμο μπορεις να φτιαξεις ενα τετοιο εργαλειο.

Δες και εδω για καποιες λυσεις

https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum

[elio_1]

Μια πολύ γρήγορη υλοποίηση, μόνο για ακέραιους:

a = int(input("Δώσε τον πρώτο ακέραιο: "))
b = int(input("Δώσε τον δεύτερο ακέραιο: "))
c = int(input("Δώσε τον τρίτο ακέραιο: "))
sumNumber = int(input("Δώσε το άθροισμα: "))
ss=0
sv=0
sb=0
total=[]
numbs = sorted((a, b, c))
div1 = int(sumNumber/numbs[0])
div2 = int(sumNumber/numbs[1])
div3 = int(sumNumber/numbs[2])
print(numbs, div1, div2, div3)

if a+b+c > sumNumber: print('Δεν Υπάρχει θετική λύση')
else :
    for i in range(div1):
        for k in range(div2):
            for j in range(div3):
                if i * numbs[0] + k * numbs[1] +j * numbs[2] > sumNumber:
                    print('άτοπο')
                    sv+=1
                elif i * numbs[0] + k * numbs[1] +j * numbs[2] == sumNumber:
                    ss+=1
                    total.append([i,k,j])
                    print("Σύνολο {}, συν1 {}, συν2 {}, συν3 {}. " .format(i * numbs[0] + k * numbs[1] +j * numbs[2], i, k, j) )
                else:
                    print('-')
                    sb+=1
print(ss, sv, sb)
print(div1, div2, div3)
print(total)

 

[The_Mentor]

Είμαι στο δρόμο και δεν μπορώ να checkάρω, αλλά νομίζω το permutations από το itertools θα σου κάνει την δουλειά. 

[Lanike71]

Βασικά είναι γραμμικό σύστημα, που έχει μόνο μία γραμμή και αυτό σημαίνει ότι αυτό μπορεί να έχει άπειρες λύσεις, αν οι παράγοντες μπορούν να είναι και αρνητικοί αριθμοί (ή έστω και θετικοί δεκαδικοί).

Μπορούν να είναι δεκαδικοί στη λύση; Αρνητικοί; 

Ψάχνεις όλες τις λύσεις;

[adi32]

13 ώρες πριν, Lanike71 είπε

Βασικά είναι γραμμικό σύστημα, που έχει μόνο μία γραμμή και αυτό σημαίνει ότι αυτό μπορεί να έχει άπειρες λύσεις, αν οι παράγοντες μπορούν να είναι και αρνητικοί αριθμοί (ή έστω και θετικοί δεκαδικοί).

Μπορούν να είναι δεκαδικοί στη λύση; Αρνητικοί; 

Ψάχνεις όλες τις λύσεις;

Μπορουν να ειναι μονο ακεραιοι θετικοι

Ψαχνω ολες τις λυσεις και ιδανικα με καποιους ορισμενους συνδυασμους 

πχ θελω

20 τεμαχια απο τα 100

20 τεμαχια απο τα 150

15 τεμαχια απο τα 250

και το αθροισμα του καθε συνδυασμου να κανει 1000

Επειδη πολλες φορες ειναι αδυνατο αυτο μπορει να μεταβληθει ο αριθμος των τεμαχιων προς τα πανω

 

Ειχα βρει και αυτο για excel αλλα κατι δε μου δουλευει

https://www.extendoffice.com/documents/excel/3557-excel-find-all-combinations-that-equal-given-sum.html

Αν θα μπορουσα να το τρεχω και σε android θα ηταν σουπερ

[DrKo]

Αυτό που ψάχνεις είναι η καμπύλη στο Ν-διάστατο χώρο με ιδιότητα

a0 + a1X1 + a2Χ2 + ... + aNXN = 0

Υπάρχουν λύσεις. 

Αφού υιοθετήσεις μία λύση, τότε μπορείς να βάλεις τα constraints σου, π.χ. 0 <= a1 <= 20. 

Επεξ/σία 21 Απριλίου 2022 από DrKo

[Lanike71]

48 λεπτά πριν, adi32 είπε

Μπορουν να ειναι μονο ακεραιοι θετικοι

Ψαχνω ολες τις λυσεις και ιδανικα με καποιους ορισμενους συνδυασμους 

πχ θελω

20 τεμαχια απο τα 100

20 τεμαχια απο τα 150

15 τεμαχια απο τα 250

και το αθροισμα του καθε συνδυασμου να κανει 1000

Επειδη πολλες φορες ειναι αδυνατο αυτο μπορει να μεταβληθει ο αριθμος των τεμαχιων προς τα πανω

 

Ειχα βρει και αυτο για excel αλλα κατι δε μου δουλευει

https://www.extendoffice.com/documents/excel/3557-excel-find-all-combinations-that-equal-given-sum.html

Αν θα μπορουσα να το τρεχω και σε android θα ηταν σουπερ

Ψάξε λίγο για γραμμικό προγραμματισμό.

Έχει και online solvers.

Wolfram|Alpha Widgets: "Linear Programming Solver" - Free Mathematics Widget (wolframalpha.com)

Edit. Γιατί κατάλαβα ότι δε θες όλες τις λύσεις, θες μία λύση που να καλύπτει κάποιες απαιτήσεις μεταξύ των συντελεστών που θα βρεις.

Επεξ/σία 21 Απριλίου 2022 από Lanike71

[adi32]

19 λεπτά πριν, Lanike71 είπε

Ψάξε λίγο για γραμμικό προγραμματισμό.

Έχει και online solvers.

Wolfram|Alpha Widgets: "Linear Programming Solver" - Free Mathematics Widget (wolframalpha.com)

Edit. Γιατί κατάλαβα ότι δε θες όλες τις λύσεις, θες μία λύση που να καλύπτει κάποιες απαιτήσεις μεταξύ των συντελεστών που θα βρεις.

Ναι ιδανικα θέλω μια λυση 

Μεχρι τωρα μεσω access εχω φτιαξει κατι και βρισκω ολους τους πιθανους συνδυασμους και επιλεγω απο εκει αλλα παιρνει χρονο 

[Lanike71]

11 λεπτά πριν, adi32 είπε

Ναι ιδανικα θέλω μια λυση 

Μεχρι τωρα μεσω access εχω φτιαξει κατι και βρισκω ολους τους πιθανους συνδυασμους και επιλεγω απο εκει αλλα παιρνει χρονο 

Τι χαρακτηριστικά έχει η καλύτερη λύση; Μπορεί να εκφραστεί μαθηματικά με περιορισμούς;

Αν ναι, τότε γραμμικός προγραμματισμός.

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

[adi32]

8 λεπτά πριν, Lanike71 είπε

Τι χαρακτηριστικά έχει η καλύτερη λύση; Μπορεί να εκφραστεί μαθηματικά με περιορισμούς;

Αν ναι, τότε γραμμικός προγραμματισμός.

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

Ειναι περισσοτερο το δευτερο :

πχ καποιος πελατης παραγγελνει 

20 τεμαχια απο τα 100

20 τεμαχια απο τα 150

15 τεμαχια απο τα 250

και πρεπει το αθροισμα των συνδυασμων να ειναι απο 980 εως 1000

Αν δε βγαινουν ακριβως του λεμε πχ πρεπει να παρεις λιγο παραπανω:

20 τεμαχια απο τα 100

22 τεμαχια απο τα 150

16 τεμαχια απο τα 250

 

 

[DrKo]

άκυρο. 

Επεξ/σία 21 Απριλίου 2022 από DrKo

[Directx]

Ενδιαφέρον πρόβλημα, από περιέργεια έγραψα έναν "επιλυτή" σε C++ Builder μεταβλητού αριθμού ποσοτήτων βασιζόμενος στην ιδέα των πολλαπλασιαστών που έθεσε ως παράδειγμα επίλυσης ο topic starter.

Το πρόγραμμα ουσιαστικά δημιουργεί έναν πίνακα στον οποίο αποθηκεύει έναν αριθμό πολλαπλασιαστών πχ. 1, 1, 1 τους οποίους προσαυξάνει γραμμικά +1 μονάδα από τα αριστερά προς τα δεξιά. Kάθε φορά που ο προηγούμενος μετρητής φτάνει στην μέγιστη τιμή _MAX_MULTIPLIER, τότε επανέρχεται στην μονάδα (1) και ο αμέσως επόμενος του προσαυξάνεται +1 κοκ.. αυτό επαναλαμβάνεται μέχρι όλοι οι μετρητές να φτάσουν στην τιμή _MAX_MULTIPLIER οπότε το πρόγραμμα ολοκληρώνεται , μέχρι να συμβεί αυτό όμως έχουν δοκιμαστεί όλοι οι πιθανοί πολλαπλασιαστές με τιμές έως και _MAX_MULTIPLIER με την ελπίδα να προκύψει κάποια επίλυση του συστήματος.

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

Έχω χρόνια να ασχοληθώ με τέτοια θέματα οπότε μπορεί να υπάρχουν καλύτερες λύσεις , επίσης το πρόγραμμα έχει δοκιμαστεί σε C++ Builder XE5 , φυσικά μπορεί να υπάρχουν σφάλματα ή άλλες αβλεψίες..

Καλή συνέχεια!

Spoiler

/*
 * Επιλυτής σε C++ by xdir
 */
#include <iostream>

#ifdef __BORLANDC__ // αφορά τον compiler μου, ίσως να μην παίζουν σε άλλους σήμερα..
#pragma hdrstop
#pragma argsused
#endif

// Σταθερά με τις ποσότητες που δηλώνουμε
#define _QUANTITY_COUNT 3
// Σταθερά με την μέγιστη τιμή που μπορεί να λάβει κάθε πολλαπλασιαστής του μετρητή (πχ. 9)
#define _MAX_MULTIPLIER 9
// Η προς εύρεση τιμή (πχ. 1000)
#define _TARGET_VALUE   1000L

int main(int argc, _TCHAR* argv[])
{
    // Πίνακας (μεγέθους _QUANTITY_COUNT) με τις προς εύρεση ποσότητες
    int Quantity[_QUANTITY_COUNT] = { 110, 200, 120  },
    // Πίνακας / μετρητής πολλαπλασιαστών μεγέθους ίσου μεγέθους με τον πίνακα ποσοτήτων
        Counter[_QUANTITY_COUNT];

    // flag τερματισμού while-loop
    bool Final = false;

    // Προετοιμασία μετρητή πολλαπλασιαστών
    for (int iCnt = 0; iCnt < _QUANTITY_COUNT; iCnt++)
        Counter[iCnt] = 1;

    while (true) {
        // Debug μετρητή πολλαπλασιαστών
        #ifdef _DEBUG_COUNTER
        for (int iCnt = 0; iCnt < _QUANTITY_COUNT; iCnt++) {
            std::cout << Counter[iCnt] << " ";
        }
        std::cout << std::endl;
        #endif

        // Υπολογισμός αθροίσματος..
        long Sum = 0;

        for (int iCnt = 0; iCnt < _QUANTITY_COUNT; iCnt++)
            Sum += (Quantity[iCnt] * Counter[iCnt]);

        /*
         * Έλεγχος αθροίσματος, αν πρόκειται για το ζητούμενο άθροισμα,
         *  εκτύπωση της λύσης στο STDOUT και τέλος προγράμματος
         */
        if (Sum == _TARGET_VALUE) {
            std::cout << "Solution: ";

            for (int iCnt = 0; iCnt < _QUANTITY_COUNT; iCnt++) {
                std::cout << "(" << Quantity[iCnt] << " * "
                                 << Counter[iCnt]
                          << (iCnt < _QUANTITY_COUNT - 1 ? ") + ": ")");
            }

            std::cout << " = " << Sum << std::endl;

            break;
        }

        // Τέλος λύσεων, δίχως εύρεση του ζητούμενου _TARGET_VALUE :-(
        if (Final) {
            std::cout << "Solution unobtainable within established parameters"
                      << std::endl;
            break;
        }

        /*
         * Προσαύξηση του πρώτου πολλαπλασιαστή +1, αν έφτασε στον μέγιστο
         *  επιτρεπτό πολλαπλασιαστή τότε προσαύξηση των αμέσως επόμενων του
         * όταν/αν πρέπει..
         */
        if (++(*Counter) > _MAX_MULTIPLIER) {
            *Counter = 1;

            // 'Flag' προσαύξησης του επόμενου πολλαπλασιαστή (από αριστερά προς δεξιά..)
            bool Advance = true;

            // Προσαύξηση κάθε επόμενου πολλαπλασιαστή? (τα δυο Advance μπορεί να γίνουν ένα για σύμπτυξη κώδικα)
            for (int iCnt = 1; iCnt < _QUANTITY_COUNT && Advance; iCnt++) {
                if (Counter[iCnt] + 1 > _MAX_MULTIPLIER) {
                    Counter[iCnt] = 1;
                    Advance = true; // ναι!
                } else {
                    Counter[iCnt]++;
                    Advance = false;// όχι..
                }
            }
        }

        /*
         * Ολοκλήρωση διαδικασίας? ναι όταν όλοι οι πολλαπλασιαστές του μετρητή
         *  φτάσουν στην τιμή _MAX_MULTIPLIER..
         */
        Final = true;

        for (int iCnt = 0; iCnt < _QUANTITY_COUNT; iCnt++) {
            if (Counter[iCnt] != _MAX_MULTIPLIER) {
                Final = false;
                break;
            }
        }
    }

    /*
     * Επίλογος.. τώρα το cin.get δεν είναι ότι πιο σταθερό καθώς εξαρτάται
     *  από το STDIN buffer αλλά ok..
     */
    std::cout << std::endl << "Press Enter to exit..";
    std::cin.get();

	return 0;
}

Επιτυχής έξοδος :

Solution: (110 * 4) + (200 * 1) + (120 * 3) = 1000

Press Enter to exit..

Ανεπιτυχής έξοδος:

Solution unobtainable within established parameters

 

 

[adi32]

Δοκιμασα αυτο σε excel 

https://www.extendoffice.com/product/kutools-for-excel/excel-find-all-combinations-that-equal-given-sum.html

αλλα μου δε βλεπω να μου βγαζει συνδυασμους με επαναλήψεις 

πχ το 100Χ10  ή το 200Χ5

 

Στις 21/4/2022 στις 9:52 ΜΜ, Directx είπε

Ενδιαφέρον πρόβλημα, από περιέργεια έγραψα έναν "επιλυτή" σε C++ Builder μεταβλητού αριθμού ποσοτήτων βασιζόμενος στην ιδέα των πολλαπλασιαστών που έθεσε ως παράδειγμα επίλυσης ο topic starter.

Το πρόγραμμα ουσιαστικά δημιουργεί έναν πίνακα στον οποίο αποθηκεύει έναν αριθμό πολλαπλασιαστών πχ. 1, 1, 1 τους οποίους προσαυξάνει γραμμικά +1 μονάδα από τα αριστερά προς τα δεξιά. Kάθε φορά που ο προηγούμενος μετρητής φτάνει στην μέγιστη τιμή _MAX_MULTIPLIER, τότε επανέρχεται στην μονάδα (1) και ο αμέσως επόμενος του προσαυξάνεται +1 κοκ.. αυτό επαναλαμβάνεται μέχρι όλοι οι μετρητές να φτάσουν στην τιμή _MAX_MULTIPLIER οπότε το πρόγραμμα ολοκληρώνεται , μέχρι να συμβεί αυτό όμως έχουν δοκιμαστεί όλοι οι πιθανοί πολλαπλασιαστές με τιμές έως και _MAX_MULTIPLIER με την ελπίδα να προκύψει κάποια επίλυση του συστήματος.

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

Έχω χρόνια να ασχοληθώ με τέτοια θέματα οπότε μπορεί να υπάρχουν καλύτερες λύσεις , επίσης το πρόγραμμα έχει δοκιμαστεί σε C++ Builder XE5 , φυσικά μπορεί να υπάρχουν σφάλματα ή άλλες αβλεψίες..

Καλή συνέχεια!

  Εμφάνιση κρυμμένου περιεχομένου

/*
 * Επιλυτής σε C++ by xdir
 */
#include <iostream>

#ifdef __BORLANDC__ // αφορά τον compiler μου, ίσως να μην παίζουν σε άλλους σήμερα..
#pragma hdrstop
#pragma argsused
#endif

// Σταθερά με τις ποσότητες που δηλώνουμε
#define _QUANTITY_COUNT 3
// Σταθερά με την μέγιστη τιμή που μπορεί να λάβει κάθε πολλαπλασιαστής του μετρητή (πχ. 9)
#define _MAX_MULTIPLIER 9
// Η προς εύρεση τιμή (πχ. 1000)
#define _TARGET_VALUE   1000L

int main(int argc, _TCHAR* argv[])
{
    // Πίνακας (μεγέθους _QUANTITY_COUNT) με τις προς εύρεση ποσότητες
    int Quantity[_QUANTITY_COUNT] = { 110, 200, 120  },
    // Πίνακας / μετρητής πολλαπλασιαστών μεγέθους ίσου μεγέθους με τον πίνακα ποσοτήτων
        Counter[_QUANTITY_COUNT];

    // flag τερματισμού while-loop
    bool Final = false;

    // Προετοιμασία μετρητή πολλαπλασιαστών
    for (int iCnt = 0; iCnt < _QUANTITY_COUNT; iCnt++)
        Counter[iCnt] = 1;

    while (true) {
        // Debug μετρητή πολλαπλασιαστών
        #ifdef _DEBUG_COUNTER
        for (int iCnt = 0; iCnt < _QUANTITY_COUNT; iCnt++) {
            std::cout << Counter[iCnt] << " ";
        }
        std::cout << std::endl;
        #endif

        // Υπολογισμός αθροίσματος..
        long Sum = 0;

        for (int iCnt = 0; iCnt < _QUANTITY_COUNT; iCnt++)
            Sum += (Quantity[iCnt] * Counter[iCnt]);

        /*
         * Έλεγχος αθροίσματος, αν πρόκειται για το ζητούμενο άθροισμα,
         *  εκτύπωση της λύσης στο STDOUT και τέλος προγράμματος
         */
        if (Sum == _TARGET_VALUE) {
            std::cout << "Solution: ";

            for (int iCnt = 0; iCnt < _QUANTITY_COUNT; iCnt++) {
                std::cout << "(" << Quantity[iCnt] << " * "
                                 << Counter[iCnt]
                          << (iCnt < _QUANTITY_COUNT - 1 ? ") + ": ")");
            }

            std::cout << " = " << Sum << std::endl;

            break;
        }

        // Τέλος λύσεων, δίχως εύρεση του ζητούμενου _TARGET_VALUE :-(
        if (Final) {
            std::cout << "Solution unobtainable within established parameters"
                      << std::endl;
            break;
        }

        /*
         * Προσαύξηση του πρώτου πολλαπλασιαστή +1, αν έφτασε στον μέγιστο
         *  επιτρεπτό πολλαπλασιαστή τότε προσαύξηση των αμέσως επόμενων του
         * όταν/αν πρέπει..
         */
        if (++(*Counter) > _MAX_MULTIPLIER) {
            *Counter = 1;

            // 'Flag' προσαύξησης του επόμενου πολλαπλασιαστή (από αριστερά προς δεξιά..)
            bool Advance = true;

            // Προσαύξηση κάθε επόμενου πολλαπλασιαστή? (τα δυο Advance μπορεί να γίνουν ένα για σύμπτυξη κώδικα)
            for (int iCnt = 1; iCnt < _QUANTITY_COUNT && Advance; iCnt++) {
                if (Counter[iCnt] + 1 > _MAX_MULTIPLIER) {
                    Counter[iCnt] = 1;
                    Advance = true; // ναι!
                } else {
                    Counter[iCnt]++;
                    Advance = false;// όχι..
                }
            }
        }

        /*
         * Ολοκλήρωση διαδικασίας? ναι όταν όλοι οι πολλαπλασιαστές του μετρητή
         *  φτάσουν στην τιμή _MAX_MULTIPLIER..
         */
        Final = true;

        for (int iCnt = 0; iCnt < _QUANTITY_COUNT; iCnt++) {
            if (Counter[iCnt] != _MAX_MULTIPLIER) {
                Final = false;
                break;
            }
        }
    }

    /*
     * Επίλογος.. τώρα το cin.get δεν είναι ότι πιο σταθερό καθώς εξαρτάται
     *  από το STDIN buffer αλλά ok..
     */
    std::cout << std::endl << "Press Enter to exit..";
    std::cin.get();

	return 0;
}

Επιτυχής έξοδος :

Solution: (110 * 4) + (200 * 1) + (120 * 3) = 1000

Press Enter to exit..

Ανεπιτυχής έξοδος:

Solution unobtainable within established parameters

 

 

Πως μπορώ να το τρέξω αυτό σε browser? 

Επεξ/σία 26 Απριλίου 2022 από adi32

[ghostaki]

Αν το πρόβλημα είναι σχετικά "περιορισμένης" φύσης, μπορείς μήπως να το λύσεις με ένα απλό trial and error;

Δηλαδή να αξιοποιήσεις τις τιμές των μεταβλητών που ήδη έχει επιλέξει ο πελάτης και να δοκιμάσεις να τις ανεβοκατεβάζεις κατά λίγες μονάδες μέχρι να πετύχεις το άθροισμα που θες; Αυτό προφανώς θα δούλευε μόνο αν τα νούμερα είναι βολικά, δηλαδή αν στην πράξη αυτό που συνήθως χρειάζεται π.χ. είναι να βάλεις μια μονάδα από το Α προιόν και να βγάλεις 2 μονάδες από το Β προιόν. 

Δηλαδή όταν ο πελάτης έχει επιλέξει 20 τεμαχια απο τα 100, 20 τεμαχια απο τα 150 και 15 τεμαχια απο τα 250, τότε κάνε ένα loop που διαδοχικά αυξάνει κατά μια μονάδα την κάθε ποσότητα μέχρι να βγει το άθροισμα που θες.

Πολύ περιορισμένο το παραπάνω και μόνο υπό προυποθέσεις θα δούλευε. Αλλά ίσως σου αρκεί, ιδιαίτερα αν δεν χρειάζεσαι πάντα 100% εγγυημένη λύση και είναι ΟΚ να βγάζεις ένα μήνυμα του στυλ "Επιλέξτε όσες μονάδες χρειάζεται για να βγεί το σύνολο ΧΧΧ"

Επεξ/σία 26 Απριλίου 2022 από ghostaki