Δυνατοί συνδυασμοί αριθμών που κάνουν συγκεκριμένο άθροισμα

[AfterForever]

Καλησπέρα.

 

Έστω ότι έχουμε ένα πίνακα Ν αριθμών και θέλουμε να βρούμε ποιοι συνδυασμοί κάνουν ένα συγκεκριμένο

άθροισμα. Προφανώς κάποιος αριθμός μπορεί να χρησιμοποιηθεί παραπάνω από μια φορά.

 

Ρίχτε καμιά ιδέα γιατί έχω κολλήσει πραγματικά. Προφανώς δε ζητάω κώδικα, απλά τη λογική ή κάποιο hint.

 

Ευχαριστώ.

 

[pmav99]

http://www.insomnia.gr/topic/552146-προσθεση-συγκεκριμενων-ακεραιων-μεχρι-μια-καθ/?p=53675116

[albNik]

Ας πουμε εχεις τους παρακατω [2, 3, 4, 10, 13] και θες να βρεις με ποσους τρόπους κανεις αθροισμα 20

Ο αριθμός αυτος ειναι ο συντελεστης του x²⁰ αφού κανεις τις παρακατω πραξεις

(1+x²+x⁴+...+x²⁰)(1+x³+...+x¹⁸)(1+x⁴+...+x²⁰)(1+x¹⁰+x²⁰)(1+x¹³)

Η ιδεα αυτη υλοποιειται ευκολα σε προγραμμα

[whodatinsomniaK]

Δεν αναφέρει οτι θέλει να το λύσει για ακέραιους μονο...

[Kercyn]

Δεν αναφέρει οτι θέλει να το λύσει για ακέραιους μονο...

 

Τι διαφορά θα είχε;

[whodatinsomniaK]

Ότι δε λύνεται·

[Kercyn]

http://en.wikipedia.org/wiki/Continuous_knapsack_problem

Αυτό δεν είναι;

 

Επίσης, μπορεί κάποιος να μου εξηγήσει γιατί το ένα είναι NP-hard και το άλλο πολυωνυμικό; Δε θα μπορούσαμε, λέω εγώ ο αφελής, να πολλαπλασιάζουμε τα πάντα με 10 μέχρι να μην έχουμε δεκαδικούς; Γιατί δεν ανάγεται στο ίδιο πρόβλημα;

[albNik]

Δεν ειναι το knapsack αυτό. Στo knapsack εχεις μια χωρητικότητα π.χ σε κιλα Ν και πρεπει να μαζεψεις αντικειμενα (τα οποια εχουν βαρος και αξια)  μεγιστης αξιας χωρις να ξεπερασεις το Ν.

 

Εδώ ολοι οι αριθμοί εχουν ιδια "αξια" και πρεπει να φερεις ακριβως Ν.

 

Και τα δυο λύνονται σε ψευδο-πολυωνυμικο χρόνο.

Ψαξε "dynamic programming pseudo polynomial".

To continuous knapsack ειναι ευκολο.

Ας πουμε εχεις 10 σακους με αλευρι διαφορων  ποιοτήτων (τιμή ανα κιλο) και πρεπει να παρεις τη μεγαλυτερη αξια.

Ξεκινας με το ακριβότερο, μετα το αμεσως πιο φτηνο ... μεχρι να φτασεις το μεγιστο βαρος.

[Lanike71]

To πρόβλημα είναι το γνωστό subset sum:

 

http://en.wikipedia.org/wiki/Subset_sum_problem

 

Και όπως αναφέρεται, είναι μία ειδική περίπτωση του knapsack problem.

 

Σε αυτό που κόλλησα είναι το ότι κάθε στοιχείο θα πρέπει να μπορεί να χρησιμοποιηθεί παραπάνω από 1 φορά...

@ :albNik :με τις γεννήτριες συναρτήσεις βγαίνει; Αν θέλω πχ sum=10 θα πρέπει να έχω και την περίπτωση χ^2 σε 5 παρενθέσεις τουλ., κάτι που σίγουρα δεν υπάρχει.

[albNik]

Σε μια παρενθεση θα βαλεις τους εκθετες πολλαπλασια του 2

(1+x²+x⁴+x⁶+x⁸+x¹⁰)

 

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

δ.λ.δ για αυτο [2, 2, 2, 3, 3, 4] 

θα γραψεις (1+x²+x⁴+x⁶)(1+x³+x⁶)(1+x⁴)

[Kercyn]

Ευχαριστώ παιδιά.

[AfterForever]

Καλησπέρα σε όλους, χρόνια πολλά και ευχαριστώ για τις απαντήσεις.

Το πρόβλημα που είχα να λύσω ήταν το εξής:

Στο παιχνίδι Darts (βελάκια) τα επιτρεπτά σκορ με ένα βέλος είναι: 
7, 15, 19, 23, 29 και 37. Στόχος του παιχνιδιού είναι να συγκεντρωθούν 100 βαθμοί 
ακριβώς με 6 βολές. Ποιοι είναι οι δυνατοί συνδυασμοί για να επιτευχθεί αυτό; 
(Θεωρήστε ότι τα 6 διαφορετικά επιτρεπτά σκορ βρίσκονται σε πίνακα ακεραίων Ρ[6]).

Το μπακαλίστικο που έκανα είναι το εξής:

Θεώρησα ότι πρέπει

α*Ρ[1]+β*Ρ[2]+γ*Ρ[3]+δ*Ρ[4]+ε*Ρ[5]+ζ*Ρ[6]=100

.

 

Οπότε πήρα εμφωλευμένα for. Αν και δε με ενδιαφέρει και πολύ η πολυπλοκότητα του αλγορίθμου, ξεκίνησα κάθε συντελεστή από το 0 και τους πήγα μέχρι μια τιμή τον καθένα, σκεπτόμενος λογικά (πχ το ζ δε μπορεί να' ναι πάνω από 2, γιατί 2*37=74 μετά δε μπορεί να προστεθεί τίποτα άλλο που να κάνει άθροισμα 100 από τους παραπάνω αριθμούς, το α δε μπορεί να' ναι παραπάνω από 11 γιατί 11*7=77+23=100 άλλος συνδυασμός δε βγαίνει). Έτσι κατέληξα, αν και έχω πολλές επαναληψεις εν τέλει (είπαμε, είναι Γ' λυκείου μια δύσκολη άσκηση ούτως ή άλλως, δε θα σκεφτώ πολυπλοκότητα) τους συντελεστές να  τους βάλω στις for ως εξής:

 

α 0-11

β 0-4

γ 0-4

δ 0-4

ε 0-3

ζ 0-2

 
for(a=0;a=11;a++)
for(b=0;b=5;b++)
...
if(α*Ρ[1]+β*Ρ[2]+γ*Ρ[3]+δ*Ρ[4]+ε*Ρ[5]+ζ*Ρ[6]=100) then print α,β,γ,δ,ε,ζ

Αν το τρέξω βγάζει αποτέλεσμα και όντως βγαίνουν όλοι (μάλλον) οι πιθανοί συνδυασμοί που κάνουν 100, και ο κάθε ένας χρησιμοποιείται από καμία ως παραπάνω από μια φορές.

 

Δε μπορώ να σκεφτώ πιο εύκολο τρόπο.

Όπως και να έχει, ευχαριστώ για τις απαντήσεις και το ενδιαφέρον!

[Directx]

Μια σκέψη.. αν έχουμε 6 πιθανές βολές με 6 πιθανούς βαθμούς και αφού η άσκηση μιλάει για συνδυασμούς (και σας δίνει ήδη τον P διατεταγμένο) ίσως το ερώτημα να λύνεται με τον υπολογισμό όλων των permutations (διατάξεων) που μπορούν να προκύψουν για τους αριθμούς του P, με εσάς να αθροίζετε n στοιχεία του P κάθε διάταξης ελέγχοντας πότε το αποτέλεσμα είναι 100.

 

Σε αυτήν την περίπτωση πάντως – θα πρέπει να γραφθεί μια συνάρτηση που να αναδιατάσσει το P (πχ.. σαν STL next_permutation) και να απορρίπτονται οι ήδη υπολογισμένες (υπό-)διατάξεις.

 

Η έξοδος που θα μπορούσε να δοθεί τότε θα ήταν κάτι σαν αυτό:

1) 15 19 29 37
2) 15 19 37 29
3) 15 29 19 37
4) 15 29 37 19
5) 15 37 19 29
6) 15 37 29 19
7) 19 15 29 37
8) 19 15 37 29
9) 19 29 15 37
[..]

Όπου το σκορ ουσιαστικά καθορίζει τι βολές πρέπει να πετύχει ο παίκτης. Επεξ/σία 26 Δεκεμβρίου 2014 από Directx

[pmav99]

 

Αν το τρέξω βγάζει αποτέλεσμα και όντως βγαίνουν όλοι (μάλλον) οι πιθανοί συνδυασμοί

 

Απλά για να συγκρίνεις, εγώ αυτούς βγάζω:

(7, 19, 37, 37)
(15, 19, 29, 37)
(19, 23, 29, 29)
(7, 7, 7, 19, 23, 37)
(7, 7, 15, 15, 19, 37)
(7, 7, 15, 19, 23, 29)
(7, 7, 19, 19, 19, 29)
(7, 15, 15, 15, 19, 29)
(7, 7, 7, 7, 7, 7, 29, 29)
(7, 7, 7, 7, 7, 19, 23, 23)
(7, 7, 7, 7, 15, 15, 19, 23)
(7, 7, 7, 7, 15, 19, 19, 19)
(7, 7, 7, 15, 15, 15, 15, 19)
(7, 7, 7, 7, 7, 7, 7, 7, 7, 37)
(7, 7, 7, 7, 7, 7, 7, 7, 15, 29)
(7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 23)
(7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 15, 15)

[AfterForever]

0   0   0   2   2   0
0   0   1   0   3   0
0   0   2   1   0   1
0   1   0   2   0   1
0   1   1   0   1   1
1   0   0   0   2   1
1   1   0   0   0   2
3   4   1   0   0   0
4   1   3   0   0   0
4   2   1   1   0   0
4   3   0   0   1   0
5   0   1   2   0   0
5   0   2   0   1   0
5   1   0   1   1   0
6   0   1   0   0   1
10   2   0   0   0   0
11   0   0   1   0   0

 

Εγώ αυτά βγάζω. Τα νούμερα είναι οι συντελεστές των εκάστοτε σκορ.