Με πόσους διαφορετικούς τρόπους μπορούμε να μετατρέψουμε ένα χαρτονόμισμα των 100€ σε «ψιλά», έχοντας μόνο
χαρτονομίσματα των 10€, 20€, και 50€; (Κατ.34/Νο.569)
Kαλημέρα! Aν βάλουμε και τα 5άρια στο πρόβλημα οι δυνατοί συνδυασμοί είναι 48. (τόσες βρήκα από τις ακέραιες λύσεις του συστήματος: 5n+10k+20m+50z=100 0<=n<=20 0<=k<=10 0<=m<=5 0<=z<=2
Το γενικό πρόβλημα των partitions (Ruecksack theorem, sub-sets,κλπ ) είναι πολύ ενδιαφέρον και δύσκολο. Yπάγονται στα ΝP-complete/incomplete προβλήματα και είναι πονοκέφαλος ακόμη και για brute force υπολογιστικές και ευριστικές μεθόδους
Δίνω το λινκ της Βίκης για το Ruecksack(Knapsack στα εγγλέζικα)problem. http://de.wikipedia.org/wiki/Rucksackproblem
Αναρτήσεις
3 σχόλια:
1*100
2*50
1*50+2*20+1*10
1*50+1*20+3*10
1*50+5*10
5*20
4*20+2*10
3*20+4*10
2*20+6*10
1*20+8*10
10*10
@Ευθυμιος Αλεξιου
Συγχαρητήρια! Η απάντησή σας είναι σωστή.
Kαλημέρα!
Aν βάλουμε και τα 5άρια στο πρόβλημα οι δυνατοί συνδυασμοί είναι 48. (τόσες βρήκα από τις ακέραιες λύσεις του συστήματος:
5n+10k+20m+50z=100
0<=n<=20
0<=k<=10
0<=m<=5
0<=z<=2
Το γενικό πρόβλημα των partitions (Ruecksack theorem, sub-sets,κλπ ) είναι πολύ ενδιαφέρον και δύσκολο.
Yπάγονται στα ΝP-complete/incomplete προβλήματα και είναι πονοκέφαλος ακόμη και για brute force υπολογιστικές και ευριστικές μεθόδους
Δίνω το λινκ της Βίκης για το Ruecksack(Knapsack στα εγγλέζικα)problem. http://de.wikipedia.org/wiki/Rucksackproblem
Δημοσίευση σχολίου