|
-
Dec 12th, 2007, 01:19 PM
#2
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
 
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|