Results 1 to 4 of 4

Thread: Mathematical Formula

  1. #1

    Thread Starter
    Frenzied Member HanneSThEGreaT's Avatar
    Join Date
    Nov 2003
    Location
    Vereeniging, South Africa
    Posts
    1,492

    Question Mathematical Formula

    Hello guys, seems like I'm making a habit of asking questions these days.

    I'm busy making an automatic exam generator, whereby I input details about the exam, then the questions and so on. It is basically at a stage where I could already implement it, but there is a feature I'd like to include, and by doing that, will make the application more user friendly.

    Let me explain. If have used / seen Microsoft Excel's Solver utility, you'd know that I can tell Solver that I'm working with x amount ( say, 500000 ), and I need to buy at least 2 big cars, 3 medium cars, and 4 small cars with that 500000. Right, so now I can set Solver's constraints in order to achieve that. It show me that I can buy 10 small cars, 6 medium cars, and 6 big cars. If I were to change the original total to 490 000, it will show me that I can buy 5 small cars, 7 medium cars, and 7 big cars.

    So now, I think I'm looking for something similar to this. Basically, I need to be able to input 50 ( the theory section's total marks ), and be able to generate an automatic point scheme, with questions counting 2 marks, 3, 4, 5, and 1. I need to be able to give all available possibilities and have used all marks. Understand what I mean ¿

    For example, if I take 25 as a total, I can have 6 questions counting 2 marks, 1 question counting 5 marks, 1 question counting 3, and another question counting 4. I need to have more than one option.

    Is there such a formula which will enable me to do this ¿
    Any advice would be appreciated!
    VB.NET MVP 2008 - Present

  2. #2
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,989

    Re: Mathematical Formula

    The problem you describe fits into the general problem known as the Backpack Problem: You have a fixed space, and a variety of different sized objects, what is the optimum number of items you can carry. In your case, you have a total number desired, which is the "fixed space", and you want to come up with a number of variously weighted items that total up to that number. Unfortunately, if you do some research on that Backpack Problem, you will discover that it has no definite solution. I saw an article many years ago that solved it for a set of items by evolving an answer using a Genetic Algorithm, but you can be pretty certain that Excel is not using a GA.

    However, you don't actually care about an optimum solution, you just want one that is "good enough". It seems like you would be able to do this by choosing "favor number" or "favor size".

    If you chose "favor number", you would look at the size remaining, and choose the smallest item that will fit. Keep doing that until you reach the maximum size. With the relatively small variation in the size of the items, this might work fairly well, but the problem would be that you might use up all of your small items, and be half of a big item away from the target such that you either add a big item and go half an item over, or leave half an item short.

    If you choose "favor size", you would do the reverse, by taking the largest item that would fit into the remaining space. This would probably get you right to your target, especially if you had plenty of "filler" items of size 1. In fact, it would always get you to your goal if you have enough fillers.

    If you wanted many options, and you have enough items at each category, it seems like you have two options:

    1) Use the second technique. Once you have a solution, any items of size N can be exchanged for other items of size N that were not used. All tests of this nature would look the same, but if you scrambled the order of the questions, they might look quite different without people recognizing that all of them have the same number of items of size N, just in a different order.

    2) Come up with a more complex variant of the second technique. One idea would be to introduce rules such as "There can not be more than x members of size N". If you impose that rule where N is 1 (the filler item), then there might be a situation where no solution can be found. If you impose enough of those rules, then there might be no solution, either. For example, if you were to have rules that there must be no more than 2 where N=5, and no more than 2 where N=4, and no more than 3 where N=3, then if the target is 50, you had better have lots of 2s and 1s, because the rules impose a cap of 27 max for the bigger items.

    Ultimately, if you made up a class with a few rules like that, built lists based on random applications of those rules, randomized the order of the lists involved, and had sufficient members of each size category that the items in the list would have a selection to choose from, you could get a very pleasing spread of options without doing any kind of non-linnear search to optimize the list.
    My usual boring signature: Nothing

  3. #3
    PowerPoster
    Join Date
    Feb 2001
    Location
    Crossroads
    Posts
    3,047

    Re: Mathematical Formula

    Sounds like your problem (as stated) could be approached using an exhaustive technique ... but it really depends on how many combinations you have for the real problem as computation time could become unbearable for large problems. I ran this code in an insignificant amount of time and got 936 possible combinations.

    It answers the question: Which combinations of quantities of 5,4,3,2,1 point questions total 25 points?

    You can also easily modify this to ignore options based on criteria (total number of questions between 3 and 10, etc) ... and, of course you can make the total points a variable user input ...

    output rows in the array are formatted as follows:
    #5 pt questions, #4 pt questions, ,#3 pt questions, ,#2 pt questions, ,#1 pt questions

    Code:
    Dim solset() As String
    ReDim solset(0)
    For i = 0 To 5
        For j = 0 To 5
            For k = 0 To 5
                For l = 0 To 5
                    For m = 0 To 5
                        For n = 0 To 5
                            If j * 5 + k * 4 + l * 3 + m * 2 + n = 25 Then
                                    ReDim Preserve solset(UBound(solset) + 1)
                                solset(UBound(solset)) = j & "," & k & "," & l & "," & m & "," & n
                            End If
                        Next n
                    Next m
                Next l
            Next k
        Next j
    Next i
    Last edited by Muddy; Dec 12th, 2007 at 07:16 PM.

  4. #4

    Thread Starter
    Frenzied Member HanneSThEGreaT's Avatar
    Join Date
    Nov 2003
    Location
    Vereeniging, South Africa
    Posts
    1,492

    Re: Mathematical Formula

    Thank you so much both of you!!
    I was thinking of having 5 sets of sequences, like :
    5,4,3,2,1
    4,3,2,1,5
    3,2,1,5,4
    2,1,5,4,3
    1,5,4,3,2

    Mostly it would amount to the same, but the difference would have come in at the last calculation. then based on the modulus, decide which can fit in.
    I also looked into loops, but I didn't have the correct formula. I'm going to try these loops ( by the looks of it, it should do what I need ), then see if I have to add some conditions based on the amount of questions.
    Thank you both once again.
    Hannes
    VB.NET MVP 2008 - Present

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width