Προσθεση συγκεκριμενων ακεραιων μεχρι μια καθορισμενη τιμη [αρχαριος][vb10]

[SOADNICK]

Καλησπερα, προσπαθω να φτιαξω ενα προγραμμα στη visual basic 2010 αλλα επειδη ειμαι αρχαριος και δε ξερω τις εντολες δυσκολευομαι.
 
 Πιο συγκεκριμενα, ας πουμε οτι εχουμε καποιους συγκεκριμενους ακεραιους, πχ 100,200,300,400 και μια μια επισης ακεραια τιμη που εισαγει ο χρηστης σε textbox. Θελω το προγραμμα να δοκιμαζει ολα τα πιθανα αθροισματα των ακεραιων που εχει (100,200 κτλπ) μεχρι να φτασει στην τιμη του χρηστη, αν πχ η τιμη ειναι 500 να βγαζει 200+300 ή 100+400. Ομως, δεν ειναι αναγκαιο να χρησιμοποιηθουν ολες οι τιμες απο μια φορα, μπορουν να μην χρησιμοποιηθουν καθολου ή να χρησιμοποιηθουν 2-3 φορες.
 
 Εστω count η τιμη που εδωσε ο χρηστης.
Θελω να γινεται το εξης:
a*100 + b*200 + c*300 + d*400 = count οπου a,b,c,d ανηκουν στο [0,3]
Αν κανενας συνδιασμος a,b,c,d δε βγαζει x να συνεχιζει με count-1 δηλαδη
a*100 + b*200 + c*300 + d*400 = count - 1 κ.ο.κ.
 

Ρωτησα και εναν φιλο μου για καμια ιδεα και μου δωσε αυτο:

integer A,B,C,D,E, count, dif, olddif, sum
do while { dif = 0 }
	{
		for A As Integer = 0 To 3 {
			for B As Integer = 0 To 3 {
				for C As Integer = 0 To 3 {
					for D As Integer = 0 To 3 {
						for E As Integer = 0 To 3 {
							sum = A*100 + B*200 + C*300 + D*400 + E*500
							dif = count - sum
							if { dif < olddif }
								save/print A,B,C,D,E
								olddif = dif
							else
							    olddif = dif
						}
					}
				}
			}
		}
	}

(Δε ξερει ομως απο visual basic ωστε να το γραψει με εντολες).
 
Καθε βοηθεια ειναι ευπροσδεκτη

Επεξ/σία 14 Δεκεμβρίου 2014 από SOADNICK

[paparovic]

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

[defacer]

Πρώτον, προσοχή γιατί το πρόβλημα που έχεις στα χέρια σου είναι το knapsack problem το οποίο στη γενική περίπτωση δεν λύνεται.

 

"Δεν λύνεται" σημαίνει ότι κανένας δεν ξέρει (και αν ήξερε, θα ήταν η μαθηματική ανακάλυψη του αιώνα) πώς να γράψει ένα πρόγραμμα το οποίο κάνει ταυτόχρονα όλα τα παρακάτω:

1. Να βρίσκει πάντα τη βέλτιστη λύση (να "γεμίζει τελείως" δηλαδή το χώρο που έχεις)
2. Να το κάνει αυτό για πλήθος αριθμών που δεν είναι πολύ μικρό (5-10-15)
3. Να το κάνει σε λογικό χρονικό διάστημα

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