Combinatorics Algorithm Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 12-21-2003, 09:00 PM Make an algorithm that, given a bunch of (n) random INTEGERs and two inputted (sp??) LONGs, where the sum of the LONGs equals the sum of the integers, finds the combination of INTEGERs for each LONG that most closely approximate (or exactly equal) the LONG's individual values. Example: INTEGERS: 5 4 2 3 = 14 LONGs: 6 8 Solution: 4 2, 5 3 Most efficient (or, the one that actually works, if there is only one that works..) algorithm wins... Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. Meg Senior Member Posts: 480 Threads: 24 Joined: Mar 2003 12-22-2003, 03:28 AM let's say the two longs = 10, 8 and the integers are 7, 2, and 9 both sets sum 18 would you want the program to say "7+2, 9" or "9+2, 7"? Both return answers (9, 9) or (11, 7) that are one away from correct. *peace* Meg. p.s. cool challenge Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 12-22-2003, 06:21 AM heh. Good question. Just any equivalent answer will do. You could just display all equivalent answers. That would be even cooler. Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 12-29-2003, 04:25 AM *swats the flies and gets rid of the giant dust balls* Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. Rhiannon Posting Freak Posts: 864 Threads: 13 Joined: Oct 2003 12-29-2003, 04:48 AM Quote:*swats the flies and gets rid of the giant dust balls* Need some help there? I've got a vacuum igitalblackie.com - Done! Ask about our hosting -Goddess of the of the No More Religion Threads movement Neo Posting Freak Posts: 1,845 Threads: 44 Joined: Aug 2002 12-29-2003, 05:42 PM Aga, I had such a question on a programming tournament (olympiad) once, and the answer is just like: Code:```[pseudocode] do    do       give highest number from the stack    loop all groups    do       give lowest number from the stack    loop all groups loop all available 'stack-numbers' [/pseudocode]``` I got many points on that question Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 12-31-2003, 01:07 AM I don't get it. Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. Neo Posting Freak Posts: 1,845 Threads: 44 Joined: Aug 2002 12-31-2003, 06:42 PM First you divide all highest numbers to all groups, then you divide all lowest numbers to each group. That should give a good answer. This is a global algorithm, there could be better answers, but take a look: LONGs: 8, 6 INTs: 5, 4, 3, 2 My algo: 5 + 2 = 7 and 4 + 3 = 7 One-of-a-time algo: 5 + 3 = 8, 4 + 2 = 6 But take a look: average of my algo is 7, the one of a time algo is 7 as well. Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 12-31-2003, 11:09 PM How would it work with this: 100 500 200 100 195 15 ? Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. SCM Senior Member Posts: 309 Threads: 15 Joined: Jul 2003 01-02-2004, 06:54 AM This is my shot at it. It's probably not optimized, but it seems to work. My strategy is to only try to fit the smaller of the two longs, and I start with the biggest integers first. If you want to try it with your own numbers, call GroupAddends with the longs in SUM(), the integers in Choices() (starting with Choices(1)), and the number of integers in n. The output is in Groups(), with the number of integers for the jth long in Groups(j, 0), and the integers starting from Groups(j, 1). Code:```DEFINT A-Z DECLARE SUB Sort (Array%(), n%) DECLARE SUB GroupAddends (Sum() AS LONG, Choices%(), n%, Groups%(), Errr%) DECLARE SUB FindAddends (Chcs%(), n%, BYVAL Total AS LONG, Sum AS LONG, Addends%(), Errr%) DIM Sum(1) AS LONG, Total AS LONG n = 14 DIM Choices(n), Groups(1, n) CLS RANDOMIZE TIMER '------------- Generate & Display Numbers ----------------- Adds0 = INT(RND * (n - 1) + 1) FOR j = 1 TO n   Choices(j) = INT(RND * 1000 + .5)   PRINT Choices(j);   IF j <= Adds0 THEN     Sum(0) = Sum(0) + Choices(j)     IF j < Adds0 THEN       PRINT "+";     ELSE       PRINT "="; Sum(0)     END IF   ELSE     Sum(1) = Sum(1) + Choices(j)     IF j < n THEN       PRINT "+";     ELSE       PRINT "="; Sum(1)     END IF   END IF NEXT PRINT '------------ End of Genrate & Display Numbers ------------ GroupAddends Sum(), Choices(), n, Groups(), Errr '-------------------  Display Results  -------------------- FOR i = 0 TO 1   Total = 0   FOR j = 1 TO Groups(i, 0) - 1     Total = Total + Groups(i, j)     PRINT Groups(i, j); "+";   NEXT   Total = Total + Groups(i, j)   PRINT Groups(i, j); "="; Total NEXT PRINT "Error ="; Errr '-------------------- End of Display results -------------- SUB FindAddends (Chcs(), n, BYVAL Total AS LONG, Sum AS LONG, Addends(), Errr)   DIM Adds(n)   Errr = 10000   j = n   DO     IF Total <= Sum THEN       IF Sum - Total < Errr THEN         Errr = Sum - Total         Addends(0) = j         FOR i = 1 TO j           Addends(i) = Chcs(i)         NEXT       END IF       EXIT SUB     ELSE       Total = Total - Chcs(j)       IF Chcs(j) < Sum THEN         FindAddends Chcs(), j - 1, Total, Sum - Chcs(j), Adds(), NewEr         IF Sum - Chcs(j) < NewEr THEN           IF Sum - Chcs(j) < Errr THEN             Addends(0) = 1             Addends(1) = Chcs(j)             Errr = Sum - Chcs(j)           END IF         ELSEIF NewEr < Errr THEN           Errr = NewEr           Addends(0) = Adds(0) + 1           FOR i = 1 TO Adds(0)             Addends(i) = Adds(i)           NEXT           Addends(Addends(0)) = Chcs(j)           IF NewEr = 0 THEN EXIT SUB         END IF       ELSE         IF Chcs(j) - Sum < Errr THEN           Errr = Chcs(j) - Sum           Addends(0) = 1           Addends(1) = Chcs(j)         END IF         IF Chcs(j) = Sum THEN EXIT SUB       END IF     END IF     j = j - 1   LOOP WHILE j > 0 END SUB SUB GroupAddends (Sum() AS LONG, Choices(), n, Groups(), Errr)   DIM Addends(n), Total AS LONG   Sort Choices(), n   Smaller = -(Sum(1) < Sum(0))   Total = Sum(0) + Sum(1)   FindAddends Choices(), n, Total, Sum(Smaller), Addends(), Errr   CIndex = 1   GIndex = 0   Groups(Smaller, 0) = Addends(0)   Groups(1 - Smaller, 0) = n - Addends(0)   FOR j = 1 TO Addends(0)     WHILE Addends(j) > Choices(CIndex)       GIndex = GIndex + 1       Groups(1 - Smaller, GIndex) = Choices(CIndex)       CIndex = CIndex + 1     WEND     Groups(Smaller, j) = Addends(j)     CIndex = CIndex + 1   NEXT   IF CIndex <= n THEN     FOR j = CIndex TO n       GIndex = GIndex + 1       Groups(1 - Smaller, GIndex) = Choices(j)     NEXT   END IF END SUB SUB Sort (Array(), n)   DO     Changes = 0     FOR j = 0 TO n - 1       IF Array(j) > Array(j + 1) THEN         SWAP Array(j), Array(j + 1)         Changes = Changes + 1       END IF     NEXT   LOOP WHILE Changes > 0 END SUB``` hrist Jesus came into the world to save sinners, of whom I am first.(I Timothy 1:15) For God so loved the world, that He gave His only begotten Son, that whoever believes in Him should not perish, but have eternal life.(John 3:16) « Next Oldest | Next Newest »