Combinatorics Algorithm - Printable Version +- Qbasicnews.com (http://qbasicnews.com/newforum) +-- Forum: QbasicNews.Com (http://qbasicnews.com/newforum/forum-3.html) +--- Forum: Challenges (http://qbasicnews.com/newforum/forum-10.html) +--- Thread: Combinatorics Algorithm (/thread-2814.html) Pages:
1
2
|
Combinatorics Algorithm - Agamemnus - 12-21-2003 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... challenge specifics: - Meg - 12-22-2003 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 Combinatorics Algorithm - Agamemnus - 12-22-2003 heh. Good question. Just any equivalent answer will do. You could just display all equivalent answers. That would be even cooler. Combinatorics Algorithm - Agamemnus - 12-29-2003 *swats the flies and gets rid of the giant dust balls* Combinatorics Algorithm - Rhiannon - 12-29-2003 Quote:*swats the flies and gets rid of the giant dust balls* Need some help there? I've got a vacuum Combinatorics Algorithm - Neo - 12-29-2003 Aga, I had such a question on a programming tournament (olympiad) once, and the answer is just like: Code: [pseudocode] I got many points on that question Combinatorics Algorithm - Agamemnus - 12-31-2003 I don't get it. Combinatorics Algorithm - Neo - 12-31-2003 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. Combinatorics Algorithm - Agamemnus - 12-31-2003 How would it work with this: 100 500 200 100 195 15 ? Combinatorics Algorithm - SCM - 01-02-2004 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 |