Java "Μεγαλητερη ποσοτητα"

[PaidiThauma]

Γεια.ηθελα να κανω ενα προγραμματακι στην Java και πανω στην τρελη χαρα κολησα πριν καν το αρχησω.το προβλημα μου ειναι το εξης.

θελω να μου υπολογιζει την καλητερη επιλογη.

δλδ.

πχ. για ενα πραγμα εχω τις τιμες (5,3,1)

για ενα αλλο (6,3,4)

και γαι τριτο (2,3,6)

και εγω εχω (150,150,150)

θελω το προγραμμα αυτο να μου υπολογιζει απο ποσα πρεπει να παρω απο το καθενα για να εχω την μεγαλητερη ποσοτητα..

πχ. 5 απο το πρωτο

4 απο το δευτερο

7 απο το τριτο.

 

κατι τετοιο.

καμια ιδεα??

[parsifal]

Δηλαδή, έχεις:

(amount1, amount2, amount3)

 

Και τα πράγματα που «αγοράζεις» έχουν τιμές/κόστη:

item1: (cost11, cost12, cost13)

item2: (cost21, cost22, cost23)

item3: (cost31, cost32, cost33)

 

Αν «αγοράσεις» x από το item1, y από το item2 και z από το item3, τότε το πρόβλημά σου μεταφράζεται ως εξής:

 

Μεγιστοποίηση της συνάρτησης f(x, y, z) = x + y + z

με constraints

x * cost11 + y * cost21 + z * cost31 <= amount1

x * cost12 + y * cost22 + z * cost32 <= amount2

x * cost13 + y * cost23 + z * cost33 <= amount3

 

 

Αυτό είναι ένα κλασσικό πρόβλημα γραμμικού προγραμματισμού. Θα πρέπει είτε να φτιάξεις μία υλοποίηση κατάλληλου αλγορίθμου που να λύνει το πρόβλημα (π.χ. Αλγόριθμος Simplex) είτε, αν δε σε ενδιαφέρει κάτι τέτοιο, να βρεις μία έτοιμη optimization library σε Java και να την χρησιμοποιήσεις στο πρόγραμμά σου.

[PaidiThauma]

hmm.πως ομως το κανω αυτο στην Java?

 

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

κανει κυκλους.

[parsifal]

Κάνε μία αναζήτηση στο Google για java simplex ή simplex in java, παίζει να βρεις κάτι έτοιμο...

[PaidiThauma]

ουφφ.

κατι βρηκα.αμα μπορεις και εχεις χρονο τσεκαρε.

http://destio.us.es/calvo/pl/ejjavasimplex/Simplex.htm

εχει ενα προγραμματακι.

το μονο προβλημα ειναι δεν ξερω ποιες τιμες βαζω που.

με τα δεδομενα που εδωσα στην αρχη μπορεις να με καθοδηγησεις?

:/

ευχαριστω.

[computeras13]

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

 

Αν δεν ξέρεις πως λειτουργεί κάτι δεν μπορείς να το φτιάξεις

[PaidiThauma]

ειδα βιντεακι στο youtube αλλα μιλουσε ενας ινδος η κατι τετοιο και δεν πολυκαταλαβαινα.

θα ηθελα να μαθω την μεθοδο αυτην αλλα οχι τωρα.

αυτην την στιγμη θελω μονο την μεθοδο αυτη σε κωδικα Java.

αμα ειναι αυτη που ανεφερα πριν τοτε θελω καποιος να μου εξηγηση.

:/

[computeras13]

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

 

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

 

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

[parsifal]

Χμμμ, τελικά ίσως ο Simplex να μην είναι η λύση. Υπάρχει ο έξτρα περιορισμός ότι οι μεταβλητές πρέπει να ανήκουν στο IN, άρα, πρόκειται για integer linear programming πρόβλημα, στα οποία εφαρμόζονται άλλοι αλγόριθμοι (Branch and Bound, Branch and Cut κ.ά.)

 

 

Πληροφοριακά, από ένα γούγλινγκ που έκανα στα πεταχτά αποκόμισα την εντύπωση ότι δεν υπάρχει και πολύ έτοιμο υλικό σε Java (με free άδεια χρήσης τουλάχιστον). Εντόπισα όμως μία βιβλιοθήκη σε C, την lp_solve, η οποία δίνεται υπό LGPL άδεια και μπορεί να χρησιμοποιηθεί από Java πρόγραμμα, αφού παρέχεται και κατάλληλος wrapper (αρχείο lp_solve_5.5.0.15_java.zip).

[PaidiThauma]

μπα.δεν βοηθαει το .pdf.

μπορει να μην σας το διατυπωσα σωστα.

θελω να γινει η σωστη χρηση των "ποντων" που εχω (150,150,150)

ετσι ωστε να μου μεινουν οι λιγοτεροι.

 

και ναι.Int θελω.

αμα σας ειναι ευκολο να ψαξετε και εσεις ενα τετοιο προγραμμα.

πληροφορικη σπουδαζω (1ο εξαμηνο) αλλα αυτο δεν εχει να κανει με αυτην.

η πληροφορικη εχει να κανει με την Java εδω.οχι ο τροπος επιλυσης.:/

 

Θα σας πω ενα καλο παραδειγμα.

εχω: 150 χρυσο

170 ασημι και

160 χαλκο.

 

ενα αλογο κανει 5 χρυσα, 4 ασημι και 5 χαλκο.

ενα ξιφος κανει 4 χρυσο, 7 ασημι και 5 χαλκο.

μια πανοπλια κανει 6 χρυσο, 6 ασημι και 6 χαλκο.

 

πειτε οτι εχω ενα στρατο με χ στρατιωτες.

θελω να παρω απο ολα και να μου μεινουν τα λιγοτερα δυνατον χρηματα.

 

Η λυση δεν ειναι μια.ειναι πολλες με διαφορες τιμες.

πχ(τυχαια νουμερα) 10 11 6

αλλη λυση μπορει να ειναι 8 10 10 κτλ.

[parsifal]

Αλλάζεις λίγο την εκφώνηση τώρα, αλλά η λογική επίλυσης είναι η ίδια:

 

Είτε μεγιστοποίηση του ποσού που θα ξοδέψεις:

max: f1(x, y, z) = (cost11 + cost12 + cost13) * x + (cost21 + cost22 + cost23) * y + (cost31 + cost32 + cost33) * z

Είτε ελαχιστοποίηση του ποσού που σου απομένει:

min: f2(x, y, z) = (amount1 - cost11 * x - cost21 * y - cost31 * z) + (amount2 - cost12 * x - cost22 * y - cost32 * z) + (amount3 - cost13 * x - cost23 * y - cost33 * z)

Το ίδιο πράγμα.

Με constraints τα ίδια ακριβώς με πριν.

 

 

Και όχι, δε μπορείς να ξέρεις εκ των προτέρων για τη γενική περίπτωση αν η λύση είναι μοναδική ή περισσότερες της μίας.

 

 

Όμως, μιας και είσαι ακόμη στο 1ο εξάμηνο των σπουδών σου και μάλλον το μάθημα του Γραμμικού Προγραμματισμού θα το αντιμετωπίσεις αρκετά αργότερα, νομίζω ότι στο στάδιο αυτό το πρόβλημα μπορείς να το λύσεις και με έναν πιο απλό μαθηματικά (και για να γράψεις τον αντίστοιχο κώδικα) τρόπο: Με παραλλαγή του Greedy/Άπληστου αλγορίθμου. Στο παράδειγμά σου δηλαδή, υπολογίζεις το μέγιστο αριθμό μόνο αλόγων, μόνο ξιφών και μόνο πανοπλιών που μπορείς να αγοράσεις. Για κάθε έναν από αυτούς, μειώνεις κάθε φορά κατά 1 και αυξάνεις όσο μπορείς τους άλλους 2 (ξεκινώντας γι' αυτούς από το 0), υπολογίζοντας κάθε φορά το ποσό που θα έμενε αν επέλεγες τον αντίστοιχο συνδυασμό αγορών. Κάτι τέτοιο δηλαδή:

 

>
...
...
for(i = MaxItem1Only; i >= 0; i--) {
   ...
   for(j = 0; PreviousJIterationOverflowed == false; j++) {
       ...
       for(k = 0; PreviousKIterationOverflowed == false; k++) {
           ...
       }
       ...
   for(k = 0; PreviousKIterationOverflowed == false; k++) {
       ...
       for(j = 0; PreviousJIterationOverflowed == false; j++) {
           ...
       }
       ...
   }
   ...
}

for(j = MaxItem2Only; j >= 0; j--) {
   ...
   for(i = 0; PreviousIIterationOverflowed == false; i++) {
       ...
       for(k = 0; PreviousKIterationOverflowed == false; k++) {
           ...
       }
       ...
   for(k = 0; PreviousKIterationOverflowed == false; k++) {
       ...
       for(i = 0; PreviousIIterationOverflowed == false; i++) {
           ...
       }
       ...
   }
   ...
}

for(k = MaxItem3Only; k >= 0; k--) {
   ...
   for(i = 0; PreviousIIterationOverflowed == false; i++) {
       ...
       for(j = 0; PreviousJIterationOverflowed == false; j++) {
           ...
       }
       ...
   for(j = 0; PreviousJIterationOverflowed == false; j++) {
       ...
       for(i = 0; PreviousIIterationOverflowed == false; i++) {
           ...
       }
       ...
   }
   ...
}
...
...

[PaidiThauma]

αυτο που ειπες το τελευταιο.αυτο εννουσα περισσοτερο απο μια λυσεις.

 

""Είτε μεγιστοποίηση του ποσού που θα ξοδέψεις:

max: f1(x, y, z) = (cost11 + cost12 + cost13) * x + (cost21 + cost22 + cost23) * y + (cost31 + cost32 + cost33) * z""

τα costs δεν μπορεις να τα προσθετεις.ειναι διαφορετικα.σαν να λες μηλα - πορτοκαλια.

θα εννοεις τα items που ειπες στην αρχη.

 

----------------------------------------------------------------

εχω: 150 χρυσο

170 ασημι και

160 χαλκο.

 

ενα αλογο κανει 5 χρυσα, 4 ασημι και 5 χαλκο.

ενα ξιφος κανει 4 χρυσο, 7 ασημι και 5 χαλκο.

μια πανοπλια κανει 6 χρυσο, 6 ασημι και 6 χαλκο.

Ετσι θα γινει?

----------------------------------------------------------------

max: f1(x, y, z) = αλογα * x + ξιφος * y + πανοπλια * z

x * 5 + y * 4 + z * 6 <= 150

x * 4 + y * 7 + z * 6 <= 170

x * 5 + y * 5 + z * 6 <= 160

----------------------------------------------------------------

 

http://destio.us.es/calvo/pl/ejjavasimplex/Simplex.htm

 

στο παραπανω προγραμμα ομως τι βαζουμε στα τρια πρωτα κουτακια??

(δεν μπορω να ανεβασω την φοτογραφια)

 

αμα καταλαβε κανεις το προγραμμα ας μου πει παρακαλω.

[parsifal]

""Είτε μεγιστοποίηση του ποσού που θα ξοδέψεις:

max: f1(x, y, z) = (cost11 + cost12 + cost13) * x + (cost21 + cost22 + cost23) * y + (cost31 + cost32 + cost33) * z""

τα costs δεν μπορεις να τα προσθετεις.ειναι διαφορετικα.σαν να λες μηλα - πορτοκαλια.

θα εννοεις τα items που ειπες στην αρχη.

 

Γιατί να μη μπορείς να τα προσθέσεις; Σταθερές δεν είναι; Αν αγοράσεις x άλογα, y ξίφη και z πανοπλίες, δε θα έχεις ξοδέψει:

 

Για τα άλογα: cost11 * x + cost12 * x + cost13 * x

Για τα ξίφη: cost21 * y + cost22 * y + cost23 * y

Για τις πανοπλίες: cost31 * z + cost32 * z + cost33 * z

 

... ;

 

Αν προσθέσεις και βγάλεις κοινούς παράγοντες, δεν παίρνεις την f1(x, y, z) που έγραψα πιο πάνω;

 

 

Ετσι θα γινει?

----------------------------------------------------------------

max: f1(x, y, z) = αλογα * x + ξιφος * y + πανοπλια * z

x * 5 + y * 4 + z * 6 <= 150

x * 4 + y * 7 + z * 6 <= 170

x * 5 + y * 5 + z * 6 <= 160

----------------------------------------------------------------

 

Με μπερδεύει η συνάρτηση f1 που έβγαλες: Αν με x, y, z συμβολίζεις τις ποσότητες που θα αγοραστούν από το κάθε είδος, τότε με τα «άλογα», «ξίφος», «πανοπλία» τί συμβολίζεις; Μήπως τα αθροίσματα (cost11 + cost12 + cost13), (cost21 + cost22 + cost23), (cost31 + cost32 + cost33); Αν ναι, τότε το ίδιο ακριβώς πράγμα δεν έχουμε γράψει και οι δύο;

 

 

http://destio.us.es/calvo/pl/ejjavasimplex/Simplex.htm

 

στο παραπανω προγραμμα ομως τι βαζουμε στα τρια πρωτα κουτακια??

(δεν μπορω να ανεβασω την φοτογραφια)

 

αμα καταλαβε κανεις το προγραμμα ας μου πει παρακαλω.

 

Το πρώτο dialog box είναι εύκολο νομίζω:

 

 

Στο δεύτερο, όπου x1, x2, x3 είναι προφανώς τα x, y, z που συζητούσαμε μέχρι τώρα:

 

 

Και ξεκινώντας τη διαδικασία:

 

 

x1 = 10, x2 = 10, x3 = 10 και το υπόλοιπο των resources που απομένει είναι μηδενικό, άρα όντως μεγιστοποιήθηκε το ποσό resources που ξόδεψες (ή αλλιώς ελαχιστοποιήθηκε το ποσό που απέμεινε, το ίδιο ακριβώς είναι).

 

 

Ήσουν τυχερός εδώ όμως, γιατί x1, x2, x3 € IN. Αν ανήκαν στο IR... ;

[PaidiThauma]

καλη η επεξηγηση σου.

αλλα δες λιγο με αυτες τις τιμες.

μου βγαζει οτι να 'ναι.

το προγραμμα το καταλαβα.ευχαριστω.

αλλα εχω την απορια γιατι δεν γινεται με αυτες τις τιμες.:/

(σε κουρασα και ευχαριστω μεχρι εδω)

[parsifal]

Εγώ πάντως βλέπω ότι για τις παραπάνω τιμές το Java applet ολοκληρώνει κανονικά τη διαδικασία μεγιστοποίησης:

 

 

x1 = 16.875

x2 = 7.175

x3 = 0

 

Με μέγιστο για την f την τιμή 2451.5