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 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
