To correct the paragraph: " You will be checking the branch B, then A, then D, lastly C (yes you need to try them because for a second level they are important, example: the branch C of the branch A (A->C) is still better than the branch B). Optimize the quadtree is matter of arranging the nodes in the tree in a way such that it is balanced. " It should be: " You will be checking the branch B, then A, then D, lastly C (yes you need to try them except for the fisrt level, because for a second level they are important, example: the branch C of the branch A (A->C) is still better than the branch D). Optimize the quadtree is matter of arranging the nodes in the tree in a way such that it is balanced. "
On 11 oct, 23:55, Theraot <[email protected]> wrote: > Hello, > > Sorry by the delay... -_- > > As I supected the order doesn't matter, then don't store it. If I > understand well, each cannon is different, then each possible solution > will be a boolean value saying "take to the ship" or "don't take to > the ship" for each cannon. [That makes a perfect case of a chromosome > for a genetic algorithm]. > > Now, to maximize the damage... yes you could do bruteforce, but we are > looking for a faster way. Let's use what we know... we know that we > can have less cannons that have more weight. And we know that we want > more cannons that do more damage. > > The only reason to do not use all the slots is when there is too much > weight. That means that you can start with anarbitrary combination and > cycle: > > if weight > max_weight then > take out worst cannon in ship > else > if used_slots < max_slots > add to ship best cannon not in ship > else > if worst cannon in ship < best cannon not in ship > weight_cap = max_weight - weight > replace worst cannon in ship with best cannon not in ship with less > than weight_cap in weight ** > else > done > end if > end if > end if > > [do not add again cannons that you have already taken out of the ship] > > To tell if a cannon is better to another, a cannon is better if it has > less weight and it's better if it does more damage. Have the cannons > sorted by both criterias. > > ** search only those cannons with a higher or equal damage and a lower > or equal weight. > > You will need a data structure that allows you to directly take an > item with that criteria, I think you need a quadtree* (http:// > en.wikipedia.org/wiki/Quadtree). > > * as a fast alternative, have a list sorted by damange and then by > weight, and iterate it. It's not the best solution, but will take you > less time to implement. > > The quadrants of the quadtree will be based on damage and weight, so > searching the next cannon with a higher or equal damage and a lower or > equal weight is just matter of walking the tree. > > Imagine you plot your cannons in the plane, where the x-axis is the > weight and the y-axis is the damage, that visualization will help you > understand how a quadtree can help. > > quadtrees are easy to make, each node will have four children nodes, > each one represent a direction: > A) weight + damage += > B) weight -= damage += > C) weight + damage - > D) weight -= damage - > > [the "+" that those there have a higher value, "-" for those with > lower, and "=" tells where those with the same value falls] > > You will be checking the branch B, then A, then D, lastly C (yes you > need to try them because for a second level they are important, > example: the branch C of the branch A (A->C) is still better than the > branch B). Optimize the quadtree is matter of arranging the nodes in > the tree in a way such that it is balanced. > > Please note that there are two ways of using quadtrees, one is making > the space a node, and the other is making the points a node. The first > one is more common as it's more easy to implement, in that way a node > can be a cannon or just "space" (in the plot) that contains cannons. > In the second case each node is a cannon so it saves space and it's > faster but it's hard to make a balanced quadtree that way. [I suspect > that eficient algorithms for that last case is still an area of > research, I may be out of date]. It's easier to implement an algorithm > that balances the quadtree only in one axis, if you are going for this > then balance on the y-axis (the damage) because it's what we want to > optimize. > > [evidently you want to start with the best cannons, they are probably > the solution, unless they exess the maximun weigh] > > That got to save you iterations. Is there any information I didn't > take into account? because any information can make the bruteforce > less brute and more inteligent. > > Theraot > > On 8 oct, 10:30, Ronny <[email protected]> wrote: > > > > > Sorry about the strange way of writing the question. > > Yes, it is a Knapsack problem. > > > You got a list of item. > > Like you have a pirate ship, and you have a lot of different cannons > > that you can outfit the ship with. The different weapons deal > > different amount of damage. > > > You have a weight constraint, or the ship will sink. > > You cannot use more cannons than the number of "weapon slots" you > > have. (Determined at runtime by choice of ship.) > > > I want to know what combinations of cannons that does the most damage, > > when you can use x number of cannons, and the combined weight is not > > more than the max limit. The order of the cannons makes no difference > > at all. > > > So in this situation I would have: > > Index > > Cannon name > > Cannon weight > > Cannon damage > > > Number of "inner loops" in a "brute force" solution is determined by > > the number of slots, set at runtime. > > Total weight has a variable for the max weight for a valid solution. > > You want to find max cannon damage. > > > On Oct 7, 12:06 pm, Theraot <[email protected]> wrote: > > > > 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 > > ... > > leer más »
