I have trouble undestranding the statement... If I got it well, you need to find a combination of items. Where each item has a value defined by a kind of item. There are a finite number of kinds of items each one with a value and a number of times it can be used. Also each item has a cost, and total of the cost must be below a certain limit. Now you want the combination that sums the maximum posible value.
Is it? I think it's a knapsack problem (http://en.wikipedia.org/wiki/ Knapsack_problem) Very similar to the Change-making problem (http://en.wikipedia.org/ wiki/Change-making_problem) Check those and see if they fit your situation. Also... could you raname "Property1", "Property2", "intMinP1" and "intMaxP2" to something more meaningful? It just helps getting me confused. Now, I think you could implement an genetic algorithm (http:// en.wikipedia.org/wiki/Genetic_algorithm) for this, but that's not a deterministic solution. If you want a deterministic solution we will need to analyse the problem futher. If the order doesn't matter in the combination (I forgot the in math terminology for that :P), then don't store any order, it will be easier to store how many of each posible kind of elements you take. My bet on optimizing this would be sorting the kinds of itmes by eficiency = value / cost, and try first those with higher eficiency until you can't take more, then the next with more eficiency. If the order doesn't matter, you can go right to the number of item you want by dividing the maximun cost by the the cost of the kind of item, round and multiply by the cost again. May be I got I wrong, but I hope that helps. Theraot On 5 oct, 12:01, Ronny <[email protected]> wrote: > Hey guys, > I’m a “basic”/hobby VB.NET user who is trying to create some code that > I think might be very complex. So I was hoping someone could help me > understand how this might be done. And it might be mostly a > mathematical question. > > I want to find an optimal solution of combinations of a quite large > data set, based on a few parameters. > > So I have a class with a few members in it. > Index as Integer ‘Just a counting index > Name as String ‘Name of the item > Value as Integer ‘The value I want the sum to be as high as > possible > Limit as Integer ‘The number of times this item can show > in one solution > Property1 as Integer ‘Property where item is excluded if less > than intMinP1 > Property2 as Integer ‘Property where the sum cannot be more than > intMaxP2 > > I have a “collection” class (if that’s the name) with an array/list of > the first class. > There is about 250 items in this list. (But since most items can be > used multiple times (limited by ‘Limit’), the total number of items to > try is a lot bigger.) > > I have a few variables. > intAvailable as Integer ‘Number of items in solution – Can be 1 to > 12 > intMinP1 as Integer ‘Minimum value of any Property1 in > solution > intMaxP2 as Integer ‘Maximum value of the sum of Property2 in > solution > > I want to know what combination of items from my list that gives the > highest Value. But none of the items can have a Property1 value less > than intMinP1. And the total sum of Property2 cannot be more than > intMaxP2. The same item from the collection can be in the solution > multiple times, but limited by the Limit property. > > The optimal solution (highest value) might be that you only use 9 > items, even if intAvailable is 10. > > My first thought is that you would need to loop through all > combinations. But with 250 items, many of them can be used multiple > times in the same solution. So you might have like 2,500 items and up > to 12 item combinations in your solution. 2,500^12 is a lot of > combinations. I know a processor can be fast with mathematical > calculations, but this sounds like an “over the night” calculation, > and not a “let’s try this, wait a minute, change some of the variables > and let’s try this way”. > > So, if I want to do “brute force” and loop through all combinations, > how can I do that? > > Also, if I want some “smart” solution, how can I do that? I’m sure > there are programs that do those calculations, and at super speed.. So > there must be solutions for it? > > Some thoughts I had: > Some smart selection that excludes any options already tried (but in a > different sequence)? > You have 2 items in your solution. If you try Item A and Item B, then > you also know Item B and Item A. > 3 items, you try Item A, Item A and Item B you also know A, B, A, and > B, A, A etc. etc. > > Some smarter algorithm that figures out if your result is getting > worse, then don’t continue with this path, you won’t find a better > solution here, and start on a different path? > > Limit the selections? > If you can use 10 items, don’t try combinations with only 2 or 3 > items. Cut it off somewhere at like 7 to 10 items. You greatly reduced > your combinations, but you could theoretically exclude the optimal > solution. > > If anyone can help me understand how this is done, I would be very > happy. > > Thanks, > Ronny
